Fetching the paper…
Reading the bibliography…
The dynamic matrix inverse problem is to maintain the inverse of a matrix undergoing element and column updates.
“All pairs shortest paths using bridging sets and rectangular matrix multiplication”
Uri Zwick · 1905
Earlier work this paper cites.
“Adjustment of an inverse matrix corresponding to a change in one element of a given matrix”
Jack Sherman and Winifred Morrison · 1950
Earlier work this paper cites.
“Gaussian Elimination is Not Optimal”
Volker Strassen · 1969
Earlier work this paper cites.
“Vermeidung von divisionen.”
Volker Strassen · 1973
Earlier work this paper cites.
“On determinants, matchings, and random algorithms”
L\’aszl\’o Lov\’asz · 1979
Earlier work this paper cites.
“Probabilistic algorithms for sparse polynomials”
Richard Zippel · 1979
Earlier work this paper cites.
“Fast Probabilistic Algorithms for Verification of Polynomial Identities”
Jacob. Schwartz · 1980
Earlier work this paper cites.
“The Complexity of Partial Derivatives”
Walter Baur and Volker Strassen · 1983
Earlier work this paper cites.
“How to compute fast a function and all its derivatives: A variation on the theorem of Baur-Strassen”
Jacques Morgenstern · 1985
Earlier work this paper cites.
“Matching is as easy as matrix inversion” Announced at STOC’87
Ketan Mulmuley, Umesh. Vazirani and Vijay. Vazirani · 1987
Earlier work this paper cites.
“Graph-Theoretic Methods in Database Theory”
Mihalis Yannakakis · 1990
Earlier work this paper cites.
“High-Probability Parallel Transitive-Closure Algorithms” Announced at SPAA’90
Jeffrey. Ullman and Mihalis Yannakakis · 1991
Earlier work this paper cites.
“Algebraic complexity theory” 315
Peter B\"urgisser, Michael Clausen and Mohammad Shokrollahi · 1997
Earlier work this paper cites.
“On Certificates and Lookahead in Dynamic Graph Problems” Announced at SODA’96
Sanjeev Khanna, Rajeev Motwani and Randall. Wilson · 1998
Earlier work this paper cites.
“Lower Bounds for Dynamic Algebraic Problems” Announced at STACS’99
Gudmund Frandsen, Johan. Hansen and Peter Miltersen · 2001
Cited alongside, same era.
“Maximum Matchings via Gaussian Elimination”
Marcin Mucha and Piotr Sankowski · 2004
Cited alongside, same era.
“Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract)”
Piotr Sankowski · 2004
Cited alongside, same era.
“Subquadratic Algorithm for Dynamic Shortest Distances”
Piotr Sankowski · 2005
Cited alongside, same era.
“Faster dynamic matchings and vertex connectivity”
Piotr Sankowski · 2007
Cited alongside, same era.
“Matrix-vector multiplication in sub-quadratic time: (some preprocessing required)”
Ryan Williams · 2007
Cited alongside, same era.
“Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs”
Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai · 2014
Later among the works it cites.
“Dynamic Matrix Rank with Partial Lookahead” Announced at FSTTCS’08
Telikepalli Kavitha · 2014
Later among the works it cites.
“New Unconditional Hardness Results for Dynamic and Online Problems”
Rapha\"el Clifford, Allan Grnlund and Kasper Larsen · 2015
Later among the works it cites.
“Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture”
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai and Thatchaphol Saranurak · 2015
Later among the works it cites.
“Efficient Inverse Maintenance and Faster Algorithms for Linear Programming”
Yin Lee and Aaron Sidford · 2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
“Towards polynomial lower bounds for dynamic problems”
Mihai Patrascu · 2010
Cited alongside, same era.
“Fast Dynamic Transitive Closure with Lookahead”
Piotr Sankowski and Marcin Mucha · 2010
Cited alongside, same era.
“Dynamic normal forms and dynamic characteristic polynomial” Announced at ICALP’08
Gudmund Frandsen and Piotr Sankowski · 2011
Cited alongside, same era.
“Fast matrix rank algorithms and applications” Announced at STOC’12
Ho Cheung, Tsz Kwok and Lap Lau · 2013
Cited alongside, same era.
“Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks”
Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai · 2013
Cited alongside, same era.
“Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems”
Amir Abboud and Virginia Williams · 2014
Cited alongside, same era.
Kasper Larsen and R. Williams · 2017
Later among the works it cites.
“Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n 1/2 - ϵ \epsilon )-time”
Danupon Nanongkai and Thatchaphol Saranurak · 2017
Later among the works it cites.
“Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time”
Danupon Nanongkai, Thatchaphol Saranurak and Christian Wulff-Nilsen · 2017
Later among the works it cites.
“Fully-dynamic minimum spanning forest with improved worst-case update time”
Christian Wulff-Nilsen · 2017
Later among the works it cites.
“Online Bipartite Matching with Amortized Replacements”
Aaron Bernstein, Jacob Holm and Eva Rotenberg · 2018
Later among the works it cites.
“Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication”
Diptarka Chakraborty, Lior Kamma and Kasper Larsen · 2018
Later among the works it cites.
“Solving Linear Programs in the Current Matrix Multiplication Time”
Michael. Cohen, Yin Lee and Zhao Song · 2018
Later among the works it cites.
“Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor”
Francois Gall and Florent Urrutia · 2018
Later among the works it cites.
“Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time” Announced at FOCS’14
Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai · 2018
Later among the works it cites.