arxiv: 2605.09917 · v1 · submitted 2026-05-11 · 💻 cs.DS

Recognition: 1 theorem link

· Lean Theorem

Dynamic Rank, Basis, and Matching

Jan van den Brand , Vishal Kumar , Daniel J. Zhang

Authors on Pith no claims yet

Pith reviewed 2026-05-12 04:23 UTC · model grok-4.3

classification 💻 cs.DS

keywords dynamic algorithmsmatrix rankmaximum matchingalgebraic algorithmsbasis maintenancerectangular matrix multiplicationdynamic graphs

0 comments

The pith

Dynamic algorithms maintain matrix rank with update times scaling only with the current rank r rather than matrix dimension n.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the first dynamic algorithms for tracking matrix rank, a column basis, and a maximum full-rank submatrix under entry or column changes. Earlier dynamic rank methods ran in time quadratic in the full dimension n, but these new methods achieve faster bounds when the rank stays small. The same framework directly supports maintaining the size of a maximum matching in a graph by treating the adjacency matrix algebraically. A reader would care because many real matrices and graphs exhibit low rank or low matching size, turning expensive quadratic updates into practical rank-dependent ones.

Core claim

We present dynamic rank algorithms whose update time scales with the matrix rank r, achieving Õ(r^{1.405}) time per entry-update and Õ(r^{1.528}+z) per column-update where z is the number of changed entries. This extends to Õ(|M|^{1.405}) edge-update time to maintain the size |M| of a maximum matching. We also give dynamic algorithms for maintaining a column-basis subject to column-updates and a maximum full-rank submatrix subject to entry-updates.

What carries the argument

Dynamic data structures that combine fast rectangular matrix multiplication with rank-dependent maintenance of bases and full-rank submatrices to support entry and column updates.

Load-bearing premise

Fast algorithms for rectangular matrix multiplication exist and can be plugged into the dynamic maintenance routines.

What would settle it

A concrete sequence of entry or column updates on an r-rank matrix where each update takes more than Õ(r^{1.405}) operations while using only known rectangular multiplication exponents.

Figures

Figures reproduced from arXiv: 2605.09917 by Daniel J. Zhang, Jan van den Brand, Vishal Kumar.

**Figure 2.** Figure 2: Base forest construction, before adding any dependence on [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** Figure 3: For S = {2, 3} the left leaves 1, 4 are connected to switch-vertices. For T = {1, 2}, the right leaves 3, 4 are connected to switch-vertices. Set S, T are the unique set of leaves after whose deletion the forest has a perfect matching (bold lines). S T 2 {1,2} 3 {3,4} 1 2 {3,4} {1,...,4} [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

**Figure 4.** Figure 4: S = {1, 2}, T = {1, 2}, C = {1, 2, 3, 4}, C′ = {1, 2}, vertices connected to switch-vertices have been removed for simplicity. Observe that S ′ = S \ {c} for c ∈ C ∩ S are the only sets of leaves whose deletion allows the blue forest to have a perfect matching. The choice of c corresponds to an augmenting path from the unmatched blue vertex to c. Likewise T ′ = T \ {c ′} for c ′ ∈ C ′ ∩ T are the possible … view at source ↗

**Figure 5.** Figure 5: Shape of matrix H (Lemma 3.1), the green and cyan diagonals are the random x1, .., xn and y1, ..., yn. The black boxes represent the non-zero entries of matrix B, which is the biadjacency matrix of the forest given in [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗

**Figure 6.** Figure 6: T1,4 and its biadjacency matrix 13 [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗

read the original abstract

We study dynamic algorithms for maintaining fundamental algebraic properties of matrices, specifically, rank, basis, and full-rank submatrices, with applications to maximum matching on dynamic graphs. Prior dynamic algorithms for rank achieve subquadratic update times but scale with the matrix dimension $n$, and could not always maintain the corresponding objects such as a basis or maximum full-rank submatrix. We present the first dynamic rank algorithms whose update time scales with the matrix rank $r$, achieving $\tilde O(r^{1.405})$ time per entry-update and $\tilde O(r^{1.528}+ z)$ per column-update, where $z$ is the number of changed entries. This extends to $\tilde O(|M|^{1.405})$ edge-update time to maintain the size $|M|$ of a maximum matching. We also give dynamic algorithms for maintaining a column-basis subject to column-updates and a maximum full-rank submatrix subject to entry-updates.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives the first dynamic algorithms for rank, basis, and full-rank submatrices whose update times scale with rank r instead of dimension n, and applies the idea to dynamic matching.

read the letter

This paper gives the first dynamic algorithms for rank, basis, and full-rank submatrices whose update times scale with rank r instead of dimension n, and applies the idea to dynamic matching. They achieve Õ(r^1.405) per entry update and Õ(r^1.528 + z) per column update, then use the same technique to maintain maximum matching size under edge updates in Õ(|M|^1.405) time. They also maintain an explicit column basis under column changes and a maximum full-rank submatrix under entry changes. Prior dynamic rank work stayed linear in n and often could not output the basis or submatrix at all, so the r-dependence is the clear advance when r is much smaller than n, which happens in many sparse or low-rank settings. The matching application follows directly and gives a concrete improvement over n-based dynamic matching bounds. The technical route is a reduction to rectangular matrix multiplication, which is how they escape the n factor. That step is the main contribution and appears to deliver the stated exponents without obvious extra polynomial blowup. One soft spot is that the bounds rest on the current best rectangular matrix multiplication exponents and on a field that supports them. The abstract does not name the exact exponent or field, so the paper must show that the reduction carries the exponents through cleanly and state the model (worst-case versus amortized, fully dynamic versus other variants). If any extra r^ε factor sneaks in or the field restricts the MM speed, the headline times weaken. These are theoretical results with no implementation or practical timing data, which is normal but means the practical payoff still needs checking. This work is aimed at people in dynamic algorithms and algebraic graph algorithms. A reader who cares about low-rank updates or dynamic matching will find the new bounds useful as a building block. It deserves a serious referee because the improvement is specific, the claims are falsifiable against prior n-dependent results, and the reduction technique can be verified in detail.

Referee Report

0 major / 3 minor

Summary. The manuscript presents the first dynamic algorithms for maintaining matrix rank, a column basis, and a maximum full-rank submatrix under entry and column updates, with update times depending on the current rank r rather than the full dimension n. It achieves Õ(r^{1.405}) time per entry update and Õ(r^{1.528} + z) time per column update (z changed entries), and extends the approach to maintain the size of a maximum matching in a dynamic graph with Õ(|M|^{1.405}) time per edge update.

Significance. If the claimed bounds hold, this constitutes a significant advance over prior dynamic rank algorithms that scaled with n. The r-dependent times are particularly valuable for low-rank matrices and sparse dynamic graphs, and the additional maintenance of bases and full-rank submatrices strengthens the contribution beyond merely tracking the numeric rank value. The reduction to fast rectangular matrix multiplication is a standard and appropriate technique in this area.

minor comments (3)

[Abstract] The abstract and introduction should explicitly state the underlying field (e.g., finite field of sufficient size or reals) and the precise dynamic model (fully dynamic vs. partially dynamic, worst-case vs. amortized guarantees).
[Abstract] Clarify whether the Õ notation hides only polylog factors in r or also additional polynomial factors in r or n; this is important for comparing the exponents 1.405 and 1.528 to the current best rectangular matrix-multiplication exponents.
[Introduction] The dynamic model for column updates should specify whether z is the number of changed entries in the updated column or the support size of the difference vector.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary and recommendation of minor revision. The report contains no major comments or criticisms, so we have no points to address point-by-point. We will make the minor revisions as suggested in the next version of the manuscript.

Circularity Check

0 steps flagged

No circularity; algorithmic bounds derived from independent reductions to known rectangular matrix multiplication

full rationale

The paper claims new dynamic algorithms for rank, basis, and matching whose update times scale with rank r by reducing the maintenance problem to fast rectangular matrix multiplication. The stated exponents (1.405, 1.528) are obtained by composing a new dynamic data structure with externally known rectangular MM exponents; no derivation step defines a quantity in terms of itself, fits a parameter on a subset and renames the fit as a prediction, or relies on a self-citation chain to establish uniqueness or an ansatz. The result is an existence claim for algorithms under standard algebraic assumptions and is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard assumptions of the dynamic-algorithms literature (fast matrix multiplication, RAM model with word size logarithmic in n) and on the existence of prior static algorithms for rank and matching; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)

standard math Fast rectangular matrix multiplication is available with the exponents used to derive the update times.
The stated exponents 1.405 and 1.528 are typical of current matrix-multiplication-based dynamic algorithms; the abstract invokes them implicitly.
domain assumption The dynamic update model permits arbitrary single-entry or single-column changes and reports the number of changed entries z.
The column-update bound is stated in terms of z, which presupposes this model.

pith-pipeline@v0.9.0 · 5455 in / 1477 out tokens · 34812 ms · 2026-05-12T04:23:04.147466+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1.2 reduction from n×n rank maintenance to r×r via Lemma 1.9 random projections; binary-search gadget matrix B_n(a,b) built from forests for full-rank submatrix (Section 3)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

75 extracted references · 75 canonical work pages

[1]

Gramoz Goranci and Monika Henzinger , title =

work page
[2]

Dynamic Algorithms for Maximum Matching Size , booktitle =

Soheil Behnezhad , editor =. Dynamic Algorithms for Maximum Matching Size , booktitle =. 2023 , url =. doi:10.1137/1.9781611977554.CH6 , timestamp =

work page doi:10.1137/1.9781611977554.ch6 2023
[3]

More Asymmetry Yields Faster Matrix Multiplication , booktitle =

Josh Alman and Ran Duan and Virginia. More Asymmetry Yields Faster Matrix Multiplication , booktitle =. 2025 , url =. doi:10.1137/1.9781611978322.63 , timestamp =

work page doi:10.1137/1.9781611978322.63 2025
[4]

Manoj Gupta and Shahbaz Khan , title =

work page
[5]

Monika Rauch Henzinger , title =. J. Algorithms , volume =

work page
[6]

Decremental Matching in General Graphs , booktitle =

Sepehr Assadi and Aaron Bernstein and Aditi Dudeja , editor =. Decremental Matching in General Graphs , booktitle =. 2022 , url =. doi:10.4230/LIPICS.ICALP.2022.11 , timestamp =

work page doi:10.4230/lipics.icalp.2022.11 2022
[7]

A framework for dynamic matching in weighted graphs , booktitle =

Aaron Bernstein and Aditi Dudeja and Zachary Langley , editor =. A framework for dynamic matching in weighted graphs , booktitle =. 2021 , url =. doi:10.1145/3406325.3451113 , timestamp =

work page doi:10.1145/3406325.3451113 2021
[8]

A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching , booktitle =

Aaron Bernstein and Sebastian Forster and Monika Henzinger , editor =. A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching , booktitle =. 2019 , url =. doi:10.1137/1.9781611975482.115 , timestamp =

work page doi:10.1137/1.9781611975482.115 2019
[9]

Faster Fully Dynamic Matchings with Small Approximation Ratios , booktitle =

Aaron Bernstein and Cliff Stein , editor =. Faster Fully Dynamic Matchings with Small Approximation Ratios , booktitle =. 2016 , url =. doi:10.1137/1.9781611974331.CH50 , timestamp =

work page doi:10.1137/1.9781611974331.ch50 2016
[10]

Fully Dynamic Matching in Bipartite Graphs , booktitle =

Aaron Bernstein and Cliff Stein , editor =. Fully Dynamic Matching in Bipartite Graphs , booktitle =. 2015 , url =. doi:10.1007/978-3-662-47672-7\_14 , timestamp =

work page doi:10.1007/978-3-662-47672-7 2015
[11]

CoRR , volume =

Emile Anand and Brand, Jan van den and Rose McCarty , title =. CoRR , volume =. 2025 , url =. doi:10.48550/ARXIV.2502.21240 , eprinttype =. 2502.21240 , timestamp =

work page doi:10.48550/arxiv.2502.21240 2025
[12]

David Peleg and Shay Solomon , editor =. Dynamic. Proceedings of the Twenty-Seventh Annual. 2016 , url =. doi:10.1137/1.9781611974331.CH51 , timestamp =

work page doi:10.1137/1.9781611974331.ch51 2016
[13]

Rounding dynamic matchings against an adaptive adversary , booktitle =

David Wajc , editor =. Rounding dynamic matchings against an adaptive adversary , booktitle =. 2020 , url =. doi:10.1145/3357713.3384258 , timestamp =

work page doi:10.1145/3357713.3384258 2020
[14]

54th Annual

Manoj Gupta and Richard Peng , title =. 54th Annual. 2013 , url =. doi:10.1109/FOCS.2013.65 , timestamp =

work page doi:10.1109/focs.2013.65 2013
[15]

Reif and Stephen R

John H. Reif and Stephen R. Tate , title =. J. Algorithms , volume =. 1997 , url =. doi:10.1006/JAGM.1995.0807 , timestamp =

work page doi:10.1006/jagm.1995.0807 1997
[16]

Dynamic Matching Algorithms Under Vertex Updates , booktitle =

Hung Le and Lazar Milenkovic and Shay Solomon and Virginia. Dynamic Matching Algorithms Under Vertex Updates , booktitle =. 2022 , url =. doi:10.4230/LIPICS.ITCS.2022.96 , timestamp =

work page doi:10.4230/lipics.itcs.2022.96 2022
[17]

Deterministic Dynamic Matching in Worst-Case Update Time , booktitle =

Peter Kiss , editor =. Deterministic Dynamic Matching in Worst-Case Update Time , booktitle =. 2022 , url =. doi:10.4230/LIPICS.ITCS.2022.94 , timestamp =

work page doi:10.4230/lipics.itcs.2022.94 2022
[18]

Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates , booktitle =

Sayan Bhattacharya and Peter Kiss and Thatchaphol Saranurak , editor =. Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates , booktitle =. 2023 , url =. doi:10.1137/1.9781611977554.CH1 , timestamp =

work page doi:10.1137/1.9781611977554.ch1 2023
[19]

CoRR , volume =

Peter Kiss , title =. CoRR , volume =. 2021 , url =. 2108.10461 , timestamp =

work page arXiv 2021
[20]

Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time , booktitle =

Shiri Chechik and Tianyi Zhang , editor =. Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time , booktitle =. 2019 , url =. doi:10.1109/FOCS.2019.00031 , timestamp =

work page doi:10.1109/focs.2019.00031 2019
[21]

Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier , booktitle =

Moses Charikar and Shay Solomon , editor =. Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier , booktitle =. 2018 , url =. doi:10.4230/LIPICS.ICALP.2018.33 , timestamp =

work page doi:10.4230/lipics.icalp.2018.33 2018
[22]

Deterministic Rounding of Dynamic Fractional Matchings , booktitle =

Sayan Bhattacharya and Peter Kiss , editor =. Deterministic Rounding of Dynamic Fractional Matchings , booktitle =. 2021 , url =. doi:10.4230/LIPICS.ICALP.2021.27 , timestamp =

work page doi:10.4230/lipics.icalp.2021.27 2021
[23]

New deterministic approximation algorithms for fully dynamic matching , booktitle =

Sayan Bhattacharya and Monika Henzinger and Danupon Nanongkai , editor =. New deterministic approximation algorithms for fully dynamic matching , booktitle =. 2016 , url =. doi:10.1145/2897518.2897568 , timestamp =

work page doi:10.1145/2897518.2897568 2016
[24]

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time , booktitle =

Soheil Behnezhad and Mahsa Derakhshan and MohammadTaghi Hajiaghayi and Cliff Stein and Madhu Sudan , editor =. Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time , booktitle =. 2019 , url =. doi:10.1109/FOCS.2019.00032 , timestamp =

work page doi:10.1109/focs.2019.00032 2019
[25]

Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms , booktitle =

Moab Arar and Shiri Chechik and Sarel Cohen and Cliff Stein and David Wajc , editor =. Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms , booktitle =. 2018 , url =. doi:10.4230/LIPICS.ICALP.2018.7 , timestamp =

work page doi:10.4230/lipics.icalp.2018.7 2018
[26]

Fully Dynamic Maximal Matching in

Surender Baswana and Manoj Gupta and Sandeep Sen , editor =. Fully Dynamic Maximal Matching in. 2011 , url =. doi:10.1109/FOCS.2011.89 , timestamp =

work page doi:10.1109/focs.2011.89 2011
[27]

Maintaining a large matching and a small vertex cover , booktitle =

Krzysztof Onak and Ronitt Rubinfeld , editor =. Maintaining a large matching and a small vertex cover , booktitle =. 2010 , url =. doi:10.1145/1806689.1806753 , timestamp =

work page doi:10.1145/1806689.1806753 2010
[28]

Hansen and Peter Bro Miltersen , title =

Gudmund Skovbjerg Frandsen and Johan P. Hansen and Peter Bro Miltersen , title =. Inf. Comput. , volume =. 2001 , url =. doi:10.1006/INCO.2001.3046 , timestamp =

work page doi:10.1006/inco.2001.3046 2001
[29]

Gudmund Skovbjerg Frandsen and Piotr Sankowski , title =. Theor. Comput. Sci. , volume =. 2011 , url =. doi:10.1016/J.TCS.2010.11.049 , timestamp =

work page doi:10.1016/j.tcs.2010.11.049 2011
[30]

Journal of the London Mathematical Society , volume=

The factorization of linear graphs , author=. Journal of the London Mathematical Society , volume=. 1947 , publisher=

work page 1947
[31]

A Decomposition Theorem for Maximum Weight Bipartite Matchings , journal =

Ming. A Decomposition Theorem for Maximum Weight Bipartite Matchings , journal =. 2001 , url =. doi:10.1137/S0097539799361208 , timestamp =

work page doi:10.1137/s0097539799361208 2001
[32]

Unifying Matrix Data Structures: Simplifying and Speeding up Iterative Algorithms , booktitle =

Brand, Jan van den , editor =. Unifying Matrix Data Structures: Simplifying and Speeding up Iterative Algorithms , booktitle =. 2021 , url =. doi:10.1137/1.9781611976496.1 , timestamp =

work page doi:10.1137/1.9781611976496.1 2021
[33]

Monochromatic Triangles, Triangle Listing and

Haotian Jiang and Tarun Kathuria and Yin Tat Lee and Swati Padmanabhan and Zhao Song , editor =. A Faster Interior Point Method for Semidefinite Programming , booktitle =. 2020 , url =. doi:10.1109/FOCS46700.2020.00089 , timestamp =

work page doi:10.1109/focs46700.2020.00089 2020
[34]

An improved cutting plane method for convex optimization, convex-concave games, and its applications , booktitle =

Haotian Jiang and Yin Tat Lee and Zhao Song and Sam Chiu. An improved cutting plane method for convex optimization, convex-concave games, and its applications , booktitle =. 2020 , url =. doi:10.1145/3357713.3384284 , timestamp =

work page doi:10.1145/3357713.3384284 2020
[35]

Cohen and Yin Tat Lee and Zhao Song , title =

Michael B. Cohen and Yin Tat Lee and Zhao Song , title =. J. 2021 , url =. doi:10.1145/3424305 , timestamp =

work page doi:10.1145/3424305 2021
[36]

Fully Dynamic Shortest Path Reporting Against an Adaptive Adversary , booktitle =

Anastasiia Alokhina and Brand, Jan van den , editor =. Fully Dynamic Shortest Path Reporting Against an Adaptive Adversary , booktitle =. 2024 , url =. doi:10.1137/1.9781611977912.108 , timestamp =

work page doi:10.1137/1.9781611977912.108 2024
[37]

Italiano , title =

Camil Demetrescu and Giuseppe F. Italiano , title =. J. 2005 , url =. doi:10.1145/1059513.1059514 , timestamp =

work page doi:10.1145/1059513.1059514 2005
[38]

Zhang , editor =

Emile Anand and Brand, Jan van den and Mehrdad Ghadiri and Daniel J. Zhang , editor =. The Bit Complexity of Dynamic Algebraic Formulas and Their Determinants , booktitle =. 2024 , url =. doi:10.4230/LIPICS.ICALP.2024.10 , timestamp =

work page doi:10.4230/lipics.icalp.2024.10 2024
[39]

On Dynamic Graph Algorithms with Predictions , booktitle =

Brand, Jan van den and Sebastian Forster and Yasamin Nazari and Adam Polak , editor =. On Dynamic Graph Algorithms with Predictions , booktitle =. 2024 , url =. doi:10.1137/1.9781611977912.126 , timestamp =

work page doi:10.1137/1.9781611977912.126 2024
[40]

Gudmund Skovbjerg Frandsen and Peter Frands Frandsen , title =. Theor. Comput. Sci. , volume =. 2009 , url =. doi:10.1016/J.TCS.2009.06.012 , timestamp =

work page doi:10.1016/j.tcs.2009.06.012 2009
[41]

Liu and Richard Peng and Maximilian Probst Gutenberg and Sushant Sachdeva , title =

Li Chen and Rasmus Kyng and Yang P. Liu and Richard Peng and Maximilian Probst Gutenberg and Sushant Sachdeva , title =. Commun. 2023 , url =. doi:10.1145/3610940 , timestamp =

work page doi:10.1145/3610940 2023
[42]

Monochromatic Triangles, Triangle Listing and

Brand, Jan van den and Yin Tat Lee and Danupon Nanongkai and Richard Peng and Thatchaphol Saranurak and Aaron Sidford and Zhao Song and Di Wang , editor =. Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs , booktitle =. 2020 , url =. doi:10.1109/FOCS46700.2020.00090 , timestamp =

work page doi:10.1109/focs46700.2020.00090 2020
[43]

Subquadratic dynamic path reporting in directed graphs against an adaptive adversary , booktitle =

Adam Karczmarz and Anish Mukherjee and Piotr Sankowski , editor =. Subquadratic dynamic path reporting in directed graphs against an adaptive adversary , booktitle =. 2022 , url =. doi:10.1145/3519935.3520058 , timestamp =

work page doi:10.1145/3519935.3520058 2022
[44]

Ho Yee Cheung and Tsz Chiu Kwok and Lap Chi Lau , title =. J. 2013 , url =. doi:10.1145/2528404 , timestamp =

work page doi:10.1145/2528404 2013
[45]

Fully Dynamic Matching: -Approximation in Polylog Update Time , booktitle =

Amir Azarmehr and Soheil Behnezhad and Mohammad Roghani , editor =. Fully Dynamic Matching: -Approximation in Polylog Update Time , booktitle =. 2024 , url =. doi:10.1137/1.9781611977912.109 , timestamp =

work page doi:10.1137/1.9781611977912.109 2024
[46]

Algorithmica , volume =

Peter Kiss , title =. Algorithmica , volume =. 2023 , url =. doi:10.1007/S00453-023-01151-X , timestamp =

work page doi:10.1007/s00453-023-01151-x 2023
[47]

Incremental (1-

Joakim Blikstad and Peter Kiss , editor =. Incremental (1-. 31st Annual European Symposium on Algorithms,. 2023 , url =. doi:10.4230/LIPICS.ESA.2023.22 , timestamp =

work page doi:10.4230/lipics.esa.2023.22 2023
[48]

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemer

Sepehr Assadi and Sanjeev Khanna and Peter Kiss , editor =. Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemer. Proceedings of the 2025 Annual. 2025 , url =. doi:10.1137/1.9781611978322.96 , timestamp =

work page doi:10.1137/1.9781611978322.96 2025
[49]

Sayan Bhattacharya and Peter Kiss and Thatchaphol Saranurak , title =. 64th. 2023 , url =. doi:10.1109/FOCS57990.2023.00095 , timestamp =

work page doi:10.1109/focs57990.2023.00095 2023
[50]

Sayan Bhattacharya and Peter Kiss and Thatchaphol Saranurak and David Wajc , title =. J. 2024 , url =. doi:10.1145/3679009 , timestamp =

work page doi:10.1145/3679009 2024
[51]

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture , booktitle =

Monika Henzinger and Sebastian Krinninger and Danupon Nanongkai and Thatchaphol Saranurak , editor =. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture , booktitle =. 2015 , url =. doi:10.1145/2746539.2746609 , timestamp =

work page doi:10.1145/2746539.2746609 2015
[52]

2013 , url =

Oren Weimann and Raphael Yuster , title =. 2013 , url =. doi:10.1145/2438645.2438646 , timestamp =

work page doi:10.1145/2438645.2438646 2013
[53]

Constructing a Distance Sensitivity Oracle in O(n

Yong Gu and Hanlin Ren , editor =. Constructing a Distance Sensitivity Oracle in O(n. 48th International Colloquium on Automata, Languages, and Programming,. 2021 , url =. doi:10.4230/LIPICS.ICALP.2021.76 , timestamp =

work page doi:10.4230/lipics.icalp.2021.76 2021
[54]

Faster Replacement Paths and Distance Sensitivity Oracles , journal =

Fabrizio Grandoni and Virginia. Faster Replacement Paths and Distance Sensitivity Oracles , journal =. 2020 , url =. doi:10.1145/3365835 , timestamp =

work page doi:10.1145/3365835 2020
[55]

Sensitive Distance and Reachability Oracles for Large Batch Updates , booktitle =

Brand, Jan van den and Thatchaphol Saranurak , editor =. Sensitive Distance and Reachability Oracles for Large Batch Updates , booktitle =. 2019 , url =. doi:10.1109/FOCS.2019.00034 , timestamp =

work page doi:10.1109/focs.2019.00034 2019
[56]

Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds , booktitle =

Brand, Jan van den and Danupon Nanongkai and Thatchaphol Saranurak , editor =. Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds , booktitle =. 2019 , url =. doi:10.1109/FOCS.2019.00036 , timestamp =

work page doi:10.1109/focs.2019.00036 2019
[57]

Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time , booktitle =

Brand, Jan van den and Danupon Nanongkai , editor =. Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time , booktitle =. 2019 , url =. doi:10.1109/FOCS.2019.00035 , timestamp =

work page doi:10.1109/focs.2019.00035 2019
[58]

Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs , booktitle =

Adam Karczmarz and Piotr Sankowski , editor =. Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs , booktitle =. 2023 , url =. doi:10.4230/LIPICS.ICALP.2023.84 , timestamp =

work page doi:10.4230/lipics.icalp.2023.84 2023
[59]

Fully Dynamic Algorithms for Transitive Reduction , booktitle =

Gramoz Goranci and Adam Karczmarz and Ali Momeni and Nikos Parotsidis , editor =. Fully Dynamic Algorithms for Transitive Reduction , booktitle =. 2025 , url =. doi:10.4230/LIPICS.ICALP.2025.92 , timestamp =

work page doi:10.4230/lipics.icalp.2025.92 2025
[60]

On Fully Dynamic Strongly Connected Components , booktitle =

Adam Karczmarz and Marcin Smulewicz , editor =. On Fully Dynamic Strongly Connected Components , booktitle =. 2023 , url =. doi:10.4230/LIPICS.ESA.2023.68 , timestamp =

work page doi:10.4230/lipics.esa.2023.68 2023
[61]

Brand, Jan van den and Sebastian Forster and Yasamin Nazari , title =. 63rd. 2022 , url =. doi:10.1109/FOCS54457.2022.00099 , timestamp =

work page doi:10.1109/focs54457.2022.00099 2022
[62]

Brand, Jan van den and Adam Karczmarz , title =. 64th. 2023 , url =. doi:10.1109/FOCS57990.2023.00142 , timestamp =

work page doi:10.1109/focs57990.2023.00142 2023
[63]

and Li, Jerry and Liu, Allen and Narayanan, Shyam , booktitle =

Brand, Jan van den and Daniel J. Zhang , title =. 64th. 2023 , url =. doi:10.1109/FOCS57990.2023.00036 , timestamp =

work page doi:10.1109/focs57990.2023.00036 2023
[64]

Adam Karczmarz and Piotr Sankowski , title =. 64th. 2023 , url =. doi:10.1109/FOCS57990.2023.00106 , timestamp =

work page doi:10.1109/focs57990.2023.00106 2023
[65]

45th Symposium on Foundations of Computer Science

Piotr Sankowski , title =. 45th Symposium on Foundations of Computer Science. 2004 , url =. doi:10.1109/FOCS.2004.25 , timestamp =

work page doi:10.1109/focs.2004.25 2004
[66]

Subquadratic Algorithm for Dynamic Shortest Distances , booktitle =

Piotr Sankowski , editor =. Subquadratic Algorithm for Dynamic Shortest Distances , booktitle =. 2005 , url =. doi:10.1007/11533719\_47 , timestamp =

work page doi:10.1007/11533719 2005
[67]

Faster dynamic matchings and vertex connectivity , booktitle =

Piotr Sankowski , editor =. Faster dynamic matchings and vertex connectivity , booktitle =. 2007 , url =

work page 2007
[68]

New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners , booktitle =

Thiago Bergamaschi and Monika Henzinger and Maximilian Probst Gutenberg and Virginia. New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners , booktitle =. 2021 , url =. doi:10.1137/1.9781611976465.110 , timestamp =

work page doi:10.1137/1.9781611976465.110 2021
[69]

Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems , booktitle =

Amir Abboud and Virginia. Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems , booktitle =. 2014 , url =. doi:10.1109/FOCS.2014.53 , timestamp =

work page doi:10.1109/focs.2014.53 2014
[70]

Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time , booktitle =

Sally Dong and Yu Gao and Gramoz Goranci and Yin Tat Lee and Richard Peng and Sushant Sachdeva and Guanghao Ye , editor =. Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time , booktitle =. 2022 , url =. doi:10.1137/1.9781611977073.7 , timestamp =

work page doi:10.1137/1.9781611977073.7 2022
[71]

Sarah Filippi, Olivier Cappe, Aur´ elien Garivier, and Csaba Szepesv´ ari

Yu Gao and Yang P. Liu and Richard Peng , title =. 62nd. 2021 , url =. doi:10.1109/FOCS52979.2021.00058 , timestamp =

work page doi:10.1109/focs52979.2021.00058 2021
[72]

Liu and Richard Peng and Aaron Sidford , editor =

Brand, Jan van den and Yu Gao and Arun Jambulapati and Yin Tat Lee and Yang P. Liu and Richard Peng and Aaron Sidford , editor =. Faster maxflow via improved dynamic spectral vertex sparsifiers , booktitle =. 2022 , url =. doi:10.1145/3519935.3520068 , timestamp =

work page doi:10.1145/3519935.3520068 2022
[73]

Liu and Thatchaphol Saranurak and Aaron Sidford and Zhao Song and Di Wang , editor =

Brand, Jan van den and Yin Tat Lee and Yang P. Liu and Thatchaphol Saranurak and Aaron Sidford and Zhao Song and Di Wang , editor =. Minimum cost flows, MDPs, and L1-regression in nearly linear time for dense instances , booktitle =. 2021 , url =. doi:10.1145/3406325.3451108 , timestamp =

work page doi:10.1145/3406325.3451108 2021
[74]

Balancing covariates in randomized experiments using the Gram-Schmidt walk , journal =

Christopher Harshaw and Fredrik S. Balancing covariates in randomized experiments using the Gram-Schmidt walk , journal =. 2019 , url =. 1911.03071 , timestamp =

work page arXiv 2019
[75]

CoRR , volume =

Yichuan Deng and Zhao Song and Omri Weinstein , title =. CoRR , volume =. 2022 , url =. doi:10.48550/ARXIV.2210.12468 , eprinttype =. 2210.12468 , timestamp =

work page doi:10.48550/arxiv.2210.12468 2022