English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The dynamic matrix inverse problem is to maintain the inverse of a matrixundergoing element and column updates. It is the main subroutine behind thebest algorithms for many dynamic problems whose complexity is not yetwell-understood, such as maintaining the largest eigenvalue, rank anddeterminant of a matrix and maintaining reachability, distances, maximummatching size, and $k$-paths/cycles in a graph. Understanding the complexity ofdynamic matrix inverse is a key to understand these problems.  In this paper, we present (i) improved algorithms for dynamic matrix inverseand their extensions to some incremental/look-ahead variants, and (ii) variantsof the Online Matrix-Vector conjecture [Henzinger et al. STOC'15] that, iftrue, imply that these algorithms are tight. Our algorithms automatically leadto faster dynamic algorithms for the aforementioned problems, some of which arealso tight under our conjectures, e.g. reachability and maximum matching size(closing the gaps for these two problems was in fact asked by Abboud and V.Williams [FOCS'14]). Prior best bounds for most of these problems date back tomore than a decade ago [Sankowski FOCS'04, COCOON'05, SODA'07; KavithaFSTTCS'08; Mucha and Sankowski Algorithmica'10; Bosek et al. FOCS'14].  Our improvements stem mostly from the ability to use fast matrixmultiplication ``one more time'', to maintain a certain transformation matrixwhich could be maintained only combinatorially previously (i.e. without fastmatrix multiplication). Oddly, unlike other dynamic problems where thisapproach, once successful, could be repeated several times (``bootstrapping''),our conjectures imply that this is not the case for dynamic matrix inverse andsome related problems. However, when a small additional ``look-ahead''information is provided we can perform such repetition to drive the bounds downfurther.

Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds