Pith. sign in

REVIEW 2 major objections 4 minor 114 references

Deterministic Dynamic Maximal Matching in Sublinear Update Time

T0 review · 2 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims the first deterministic fully dynamic algorithm for maximal matching with sublinear amortized update time, $\tilde{O}(n^{8/9})$, breaking the long-standing $\Omega(n)$ barrier on dense graphs.

desk verdict Breaks the Omega(n) barrier for deterministic fully dynamic maximal matching with a novel EDCS-based framework; the main risk is a cited, unproved refined ES-tree guarantee that the deterministic half depends on. read the letter →

arxiv 2504.20780 v2 pith:VBMBHK24 submitted 2025-04-29 cs.DS

Aaron Bernstein , Sayan Bhattacharya , Peter Kiss , Thatchaphol Saranurak This is my paper · ORCID
classification cs.DS
keywords fullydynamicalgorithmsmaximalmatchingedge-degreeconstrainedsubgraphdegreegapleft-perfectEven-Shiloachtreeadaptiveadversarysublinearupdatetime
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Fully dynamic maximal matching asks to keep a maximal matching as edges are inserted and deleted. Until now, every deterministic algorithm needed $\Omega(n)$ time per update in dense graphs. This paper claims the first deterministic algorithm with sublinear amortized update time, $\tilde{O}(n^{8/9})$, and a randomized variant with $\tilde{O}(n^{3/4})$ that is correct with high probability even against an adaptive adversary. The barrier breaks because the algorithm maintains a small set of high-degree vertices, matches all of them cheaply using the degree structure of an edge-degree constrained subgraph, and then only needs to scan the remaining low-degree graph.

What carries the argument

The load-bearing object is the edge-degree constrained subgraph (EDCS): a subgraph $H$ of $G$ where every kept edge has degree-sum at most $B$ and every omitted edge has degree-sum at least $(1-\epsilon)B$. The paper uses it in a new way, not to approximate maximum matching but to force a bipartite high-low subgraph with a $\gamma$-degree gap: every high vertex has degree at least $X$, every low vertex at most $(1-\gamma)X$. That gap gives Hall's condition with slack and guarantees short augmenting paths, which a left-perfect-matching data structure exploits: deterministically through a monotone dynamic shortest-path tree on the residual graph, and randomly through matching-walks that behave like random walks on an Eulerian expander.

What would settle it

Run the deterministic left-perfect-matching data structure on a degree-gap bipartite graph for one epoch with $q_{\mathrm{ep}}=\sqrt{n\gamma}$ deletions of matched edges, recording every vertex's distance to the sink; if more than $O(q_{\mathrm{ep}}/\gamma)$ vertices ever have maximum distance $\omega(\log n/\gamma)$, or if any allowed reverse-edge insertion decreases a distance to the sink, the structural lemma behind the $\tilde{O}(n^{8/9})$ bound is false.

Watch

Extended reading notes

Core claim

The central claim is that maximal matching is not intrinsically $\Omega(n)$ per update: one can keep a maximal matching deterministically in $\tilde{O}(n^{8/9})$ amortized update time, and with randomness in $\tilde{O}(n^{3/4})$ against an adaptive adversary. The algorithm splits the vertex set into high and low parts. A subgraph with a degree gap makes the high part expand into the low part, so a matching covering all safe high vertices can be maintained in sublinear time; once every high vertex is matched, an unmatched vertex only needs to scan low-degree neighbors. This converts maximal matching into a small core problem plus a low-degree boundary problem.

Load-bearing premise

The deterministic half of the paper depends on a refined accounting guarantee for a dynamic shortest-path tree to a sink, namely total update time $O(\text{total updates} + \sum_v \deg_{\max}(v)\,\operatorname{dist}_{\max}(v,t))$ including a vertex-removal operation, which the paper treats as an easy consequence of earlier algorithms rather than proving in its own text.

Editorial extensions

If this is right

  • In dense graphs, the deterministic update time drops below $n$, so the trivial $O(n)$ scan is no longer the best known deterministic solution.
  • The randomized $\tilde{O}(n^{3/4})$ bound removes the usual oblivious-adversary assumption for fast dynamic maximal matching.
  • Full edge insertions and deletions are both absorbed at the same asymptotic update time via a phase partition into a decremental core and a small set of new edges.
  • If the internal left-perfect-matching routine for degree-gap graphs could match the static $\tilde{O}(m/\gamma)$ time deterministically, the authors' decomposition would immediately give an $\tilde{O}(n^{4/5})$ update time.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The EDCS degree-gap trick is likely reusable: any dynamic problem whose hard part can be isolated behind a subgraph with Hall slack could use the same left-perfect core plus low-degree boundary decomposition.
  • The phase-based amortization suggests the approach cannot reach below roughly $\sqrt{n}$ without a new idea; the next test is whether the amortization can be deamortized to obtain worst-case sublinear updates.
  • A direct stress test of the refined dynamic-shortest-path guarantee, total update time proportional to $\sum_v \deg_{\max}(v)\,\operatorname{dist}_{\max}(v,t)$ under delete, reverse-insertion, and remove operations, would be valuable independently of the rest of the algorithm, since the deterministic bound leans on it.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper presents a fully dynamic maximal matching algorithm with a deterministic O~(n^{8/9}) amortized update time and a randomized O~(n^{3/4}) amortized update time that is correct with high probability against an adaptive adversary. The approach maintains an EDCS, classifies vertices by EDCS degree into high/medium/low sets, and reduces the task of matching all high-degree vertices to maintaining a left-perfect matching in a bipartite graph with a degree gap. This left-perfect matching is maintained either by random alternating walks (randomized version) or by a deterministic residual-graph shortest-path tree using a refined Even-Shiloach guarantee (deterministic version). A maximal matching in the remaining adjunct graph is maintained by exploiting the low arboricity of that graph. The claimed result would be the first deterministic sublinear update time for fully dynamic maximal matching and would answer a long-standing open problem.

Significance. If the deterministic analysis is complete, this is a landmark result for dynamic graph algorithms: it breaks the Omega(n) deterministic barrier for maximal matching in dense graphs and introduces a genuinely new use of the EDCS. The randomized half is well supported by the random-walk argument on Eulerian expanders, and the overall phase-based accounting is coherent and parameter-free. The paper also gives an honest discussion of limitations and open problems. However, the deterministic half currently rests on a load-bearing refined Even-Shiloach guarantee that is asserted rather than proved, and there is a clear algebraic/typographical error in the formula that drives the deterministic exponent. These issues must be fixed before the deterministic n^{8/9} claim is established.

major comments (2)
  1. [Section 5.3, Theorem 5.7] Theorem 5.7 is the sole engine for the deterministic Left Perfect Matching bound in Lemma 5.1(1), but it is not proved. The paragraph "Comparison to Standard ES guarantees" asserts that the refined guarantee follows easily from [SE81, Kin99]; this is not a routine consequence for the setting used here, which involves positive integer weights, insertions that merely do not decrease distances, and a batch Remove(v) operation. In particular, the claim that removing v by deleting all incident edges "in a single batch" costs only O(degmax(v) * distmax(v,t)) does not by itself account for distance increases at other vertices whose shortest paths used v; that work must be charged somewhere, and the cited standard ES analyses do not explicitly provide this accounting for weighted graphs with Remove(v). Since Lemma 5.20 and hence the deterministic O~(n^{8/9}) bound in Theorem 1.1 depend entirely on Theorem 5.7, the authors must supply a full proof of Theorem 5.7 or replace it by a published theorem with exactly the stated guarantees. The randomized half is not exposed to this issue.
  2. [Lemma 5.1(1) and Section 6.3.5] There is a serious formula/typo problem in the deterministic total update time. Lemma 5.1(1) states a factor (1 + u*sqrt(n*gamma)), but the proof of that lemma uses q_ep = sqrt(n*gamma) and obtains (1 + u/q_ep) epochs, i.e., (1 + u/sqrt(n*gamma)). The derivation in the proof of Lemma 6.6 exhibits the same inconsistency: it writes O~( (nB/delta) * (delta*n*sqrt(n*delta)) ) and claims this equals O~( B*n^{1/2}*delta^{-3/2} * delta*n ). The left-hand side simplifies to B*n^{5/2}*delta^{1/2}, whereas the right-hand side is B*n^{3/2}*delta^{-1/2}; these differ by a factor of n*delta. With the printed formulas and B=n^{2/9}, delta=n^{-1/9}, the deterministic amortized update time would be O~(n^{16/9}), not O~(n^{8/9}). If the intended factor is u/sqrt(n*gamma), as the proof in Section 5.3.4 strongly indicates, then the deterministic n^{8/9} balance works. Both Lemma 5.1(1) and the display in Lemma 6.6 must be corrected, and the proof must be consistent with the corrected statement.
minor comments (4)
  1. [Section 5.3.2, Observation 5.10] As written, Observation 5.10 says that T is still a shortest path tree "to v" after adding (v,u), but T is a tree to the sink t and the subsequent use in Algorithm 1 requires that no distances to t decrease. This appears to be a typo; please restate the observation as "T remains a shortest path tree to t" and justify it for weighted edges.
  2. [Section 5.3.5, Claim 5.21] The notation L_i(v) is introduced with a parameter v that is never used; it should just be L_i. This is confusing because v is also used for vertices in R.
  3. [Section 5.3.4, Claim 5.19] The sentence "each LPM.Delete adss at most one vertex to Raff" contains a typo ("adss" should be "adds").
  4. [Section 6.4, Corollary 6.16] In the proof of Corollary 6.16, the text says "bounding the number of incident edges on v in Gres"; from context this should be Gadj, not Gres.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main theorem is derived from external black boxes (EDCS maintenance, static coloring/matching, and Even-Shiloach trees) without fitted inputs or self-citation loops.

full rationale

The derivation chain is self-contained relative to the external results it cites. Theorem 1.1 is built from (i) EDCS maintenance by [GSSU22a], (ii) Lemma 3.1 matching high-degree vertices via [Ass24] and [EK24], and (iii) Lemma 5.1, which maintains a left-perfect matching either by random augmenting paths with an expander analysis proved in Sections 5.1–5.2, or by a decremental shortest-path argument that invokes the Even-Shiloach/King dynamic shortest-path structure. The randomized branch contains its own structural proofs (Lemma 5.2, Lemma 5.3, Lemma 5.17) and an appendix proof of the Eulerian random-walk convergence theorem used inside them. The deterministic branch depends on Theorem 5.7, a refined Even-Shiloach guarantee cited to [SE81, Kin99]; the paper states this as a refinement of known algorithms rather than proving it in full. That is a verification risk, not circularity, because the cited guarantee does not embed the target maximal-matching result and its assumptions (decremental graph, monotone insertions, a sink, and distance-monotone edge weights) are stated independently of Theorem 1.1. No parameter is fitted to a dataset and then renamed a prediction: the choices of B and delta are asymptotic optimization variables substituted into the final O-tilde bounds. The paper also does not import any uniqueness theorem from the authors' own prior work to force its algorithmic choice, and it does not rename a known empirical pattern as a new derivation. Hence no circular step can be exhibited.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The main theorem is constructive. The algorithmic parameters B, delta, and gamma are chosen explicitly to balance phase costs rather than fitted to external data, so the free-parameter ledger is empty. The proof imports several known data-structure and graph-theory results as black boxes; the most delicate is the Even-Shiloach tree guarantee. No new physical or external entities are introduced.

assumptions (6)
  • domain assumption A (B, B(1-epsilon))-EDCS of a dynamic graph can be maintained deterministically in O(n/(B*epsilon)) worst-case update time, with degree changes in at most two vertices per update [GSSU22a].
    Used in Section 6.1 to obtain the n/(delta*B) EDCS overhead and to define the degree-gap classification.
  • domain assumption Given adjacency list and matrix access, there exists a randomized near-linear-time algorithm that matches every maximum-degree vertex except with probability at most 2/Delta [Ass24].
    Black box used in Appendix B for the randomized version of Lemma 3.1, which initializes the base matching at the start of each phase.
  • domain assumption A deterministic Delta(1+epsilon)-edge-coloring of a graph with maximum degree Delta can be computed in O(m log n / epsilon) time [EK24].
    Black box used in Appendix B for the deterministic version of Lemma 3.1.
  • domain assumption A monotone Even-Shiloach tree maintains a shortest-path tree to a sink under deletions and insertions that do not decrease any distance, with total update time O(total updates + sum_v degmax(v) * distmax(v, t)) [SE81, Kin99].
    Used in Section 5.3 to maintain augmenting paths deterministically; this is the most load-bearing imported guarantee for the deterministic bound.
  • standard math Conductance and random-walk mixing lemmas from [RTV06, ACP16], including the stationary distribution of Eulerian Markov chains, as used in Appendix A.
    These are standard spectral facts used to prove random-walk bounds for the randomized Left Perfect Matching algorithm.
  • standard math Hall's theorem, applied through the degree gap so that every subset S of the left side has at least (1+gamma)|S| neighbors.
    Guarantees left-perfect matchings exist and is used in the structural lemmas of Section 5, including Lemma 5.17.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Deterministic Dynamic Maximal Matching in Sublinear Update Time." pith.science (2026). https://pith.science/paper/VBMBHK24

@misc{pith2026250420780,
  author       = {Pith},
  title        = {Pith review of: Deterministic Dynamic Maximal Matching in Sublinear Update Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VBMBHK24}},
  note         = {Machine review of arXiv:2504.20780}
}
abstract

We give a fully dynamic deterministic algorithm for maintaining a maximal matching of an $n$-vertex graph in $\tilde{O}(n^{8/9})$ amortized update time. This breaks the long-standing $\Omega(n)$-update-time barrier on dense graphs, achievable by trivially scanning all incident vertices of the updated edge, and affirmatively answers a major open question repeatedly asked in the literature [BGS15, BCHN18, Sol22]. We also present a faster randomized algorithm against an adaptive adversary with $\tilde{O}(n^{3/4})$ amortized update time. Our approach employs the edge degree constrained subgraph (EDCS), a central object for optimizing approximation ratio, in a completely novel way; we instead use it for maintaining a matching that matches all high degree vertices in sublinear update time so that it remains to handle low degree vertices rather straightforwardly. To optimize this approach, we employ tools never used in the dynamic matching literature prior to our work, including sublinear-time algorithms for matching high degree vertices, random walks on directed expanders, and the monotone Even-Shiloach tree for dynamic shortest paths.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

114 extracted references · 66 canonical work pages

  1. [1]

    Towards a unified theory of sparsification for matching problems

    Sepehr Assadi and Aaron Bernstein. Towards a unified theory of sparsification for matching problems. In Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA) , pages 11:1--11:20, 2019

    2019

  2. [2]

    Robust communication complexity of matching: Edcs achieves 5/6 approximation

    Amir Azarmehr and Soheil Behnezhad. Robust communication complexity of matching: Edcs achieves 5/6 approximation. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2023

    2023

  3. [3]

    Coresets meet edcs: algorithms for matching and vertex cover on massive graphs

    Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein. Coresets meet edcs: algorithms for matching and vertex cover on massive graphs. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1616--1635, 2019

    2019

  4. [4]

    Mirrokni, and Cliff Stein

    Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, and Cliff Stein. Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019 , pages 1616--1635. S...

    2019

  5. [5]

    Decremental matching in general graphs

    Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja. Decremental matching in general graphs. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France , volume 229 of LIPIcs , pages 11:1--11:19. Schloss Dagstuhl - Leibniz-Zentrum f \...

    2022

  6. [6]

    A fast and simple randomized parallel algorithm for the maximal independent set problem

    Noga Alon, L \'a szl \'o Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of algorithms , 7(4):567--583, 1986

    1986

  7. [7]

    On regularity lemma and barriers in streaming and dynamic matching

    Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, and Huan Li. On regularity lemma and barriers in streaming and dynamic matching. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023 , pages 131--144. ACM , 2023

    2023

  8. [8]

    Fully dynamic matching: (2- 2 ) -approximation in polylog update time

    Amir Azarmehr, Soheil Behnezhad, and Mohammad Roghani. Fully dynamic matching: (2- 2 ) -approximation in polylog update time. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024 , pages 3040--3061. SIAM , 2024

    2024

Show all 114 references
  1. [9]

    Dynamic matching: Reducing integral algorithms to approximately-maximal fractional algorithms

    Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, and David Wajc. Dynamic matching: Reducing integral algorithms to approximately-maximal fractional algorithms. In Ioannis Chatzigiannakis, Christos Kaklamanis, Daniel Marx, and Donald Sannella, editors, 45th International Col...

    2018

  2. [10]

    Extreme values of the stationary distribution of random walks on directed graphs

    Sinan Aksoy, Fan Chung, and Xing Peng. Extreme values of the stationary distribution of random walks on directed graphs. Advances in Applied Mathematics , 81:128--155, 2016

    2016

  3. [11]

    Network decomposition and locality in distributed computation

    Baruch Awerbuch, Andrew V Goldberg, Michael Luby, and Serge A Plotkin. Network decomposition and locality in distributed computation. In FOCS , volume 30, pages 364--369. Citeseer, 1989

    1989

  4. [12]

    The stochastic matching problem with (very) few queries

    Sepehr Assadi, Sanjeev Khanna, and Yang Li. The stochastic matching problem with (very) few queries. ACM Trans. Economics and Comput. , 7(3):16:1--16:19, 2019

    2019

  5. [13]

    Breaking the cubic barrier for all-pairs max-flow: Gomory-hu tree in nearly quadratic time

    Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi. Breaking the cubic barrier for all-pairs max-flow: Gomory-hu tree in nearly quadratic time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , p...

    2022

  6. [14]

    All-pairs max-flow is no harder than single-pair max-flow: Gomory-hu trees in almost-linear time

    Amir Abboud, Jason Li, Debmalya Panigrahi, and Thatchaphol Saranurak. All-pairs max-flow is no harder than single-pair max-flow: Gomory-hu trees in almost-linear time. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 2204--2212. IEEE, 2023

    2023

  7. [15]

    Faster vizing and near-vizing edge coloring algorithms

    Sepehr Assadi. Faster vizing and near-vizing edge coloring algorithms. arXiv preprint arXiv:2405.13371 , 2024

    2024 arXiv

  8. [16]

    Fully-dynamic graph sparsifiers against an adaptive adversary

    Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-dynamic graph sparsifiers against an adaptive adversary. arXiv preprint arXiv:2004.08432 , 2020

    2004 arXiv

  9. [17]

    Lower bounds for maximal matchings and maximal independent sets

    Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mika \"e l Rabie, and Jukka Suomela. Lower bounds for maximal matchings and maximal independent sets. Journal of the ACM (JACM) , 68(5):1--30, 2021

    2021

  10. [18]

    Deterministic decremental single source shortest paths: beyond the o (mn) bound

    Aaron Bernstein and Shiri Chechik. Deterministic decremental single source shortest paths: beyond the o (mn) bound. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pages 389--397, 2016

    2016

  11. [19]

    Deterministic partially dynamic single source shortest paths for sparse graphs

    Aaron Bernstein and Shiri Chechik. Deterministic partially dynamic single source shortest paths for sparse graphs. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 453--469. SIAM, 2017

    2017

  12. [20]

    Matching composition and efficient weight reduction in dynamic matching

    Aaron Bernstein, Jiale Chen, Aditi Dudeja, Zachary Langley, Aaron Sidford, and Ta-Wei Tu. Matching composition and efficient weight reduction in dynamic matching. arXiv preprint arXiv:2410.18936 , 2024. To appear at SODA'25

    2024 arXiv

  13. [21]

    Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time

    Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger. Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time. In Friedrich Eisenbrand and Jochen K \" o nemann, editors, Integer Programming and Combinatorial Optimiz...

    2017

  14. [22]

    Dynamic algorithms for graph coloring

    Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai. Dynamic algorithms for graph coloring. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, ...

    2018

  15. [23]

    Almost-linear time algorithms for decremental graphs: Min-cost flow and more via duality

    Jan van den Brand, Li Chen, Rasmus Kyng, Yang P Liu, Simon Meierhans, Maximilian Probst Gutenberg, and Sushant Sachdeva. Almost-linear time algorithms for decremental graphs: Min-cost flow and more via duality. arXiv preprint arXiv:2407.10830 , 2024

    2024 arXiv

  16. [24]

    Fully dynamic maximal independent set with polylogarithmic update time

    Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. Fully dynamic maximal independent set with polylogarithmic update time. In Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS) , pages 382--405, 2019

    2019

  17. [25]

    A framework for dynamic matching in weighted graphs

    Aaron Bernstein, Aditi Dudeja, and Zachary Langley. A framework for dynamic matching in weighted graphs. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , pag...

    2021

  18. [26]

    Dynamic algorithms for maximum matching size

    Soheil Behnezhad. Dynamic algorithms for maximum matching size. In Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , page To appear in, 2023

    2023

  19. [27]

    Dynamic algorithms for maximum matching size

    Soheil Behnezhad. Dynamic algorithms for maximum matching size. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 , pages 129--162. SIAM , 2023

    2023

  20. [28]

    The locality of distributed symmetry breaking

    Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. Journal of the ACM (JACM) , 63(3):1--45, 2016

    2016

  21. [29]

    The locality of distributed symmetry breaking

    Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. J. ACM , 63(3):20:1--20:45, 2016

    2016

  22. [30]

    Deterministic partially dynamic single source shortest paths in weighted graphs

    Aaron Bernstein. Deterministic partially dynamic single source shortest paths in weighted graphs. arXiv preprint arXiv:1705.10097 , 2017

    2017 arXiv

  23. [31]

    Improved bounds for matching in random-order streams

    Aaron Bernstein. Improved bounds for matching in random-order streams. Theory Comput. Syst. , 68(4):758--772, 2024

    2024

  24. [32]

    A deamortization approach for dynamic spanner and dynamic maximal matching

    Aaron Bernstein, Sebastian Forster, and Monika Henzinger. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Trans. Algorithms , 17(4):29:1--29:51, 2021

    2021

  25. [33]

    Fully dynamic maximal matching in O ( n) update time

    Surender Baswana, Manoj Gupta, and Sandeep Sen. Fully dynamic maximal matching in O ( n) update time. In Proceedings of the 52nd Symposium on Foundations of Computer Science (FOCS) , pages 383--392, 2011

    2011

  26. [34]

    Fully dynamic maximal matching in o( (n)) update time

    Surender Baswana, Manoj Gupta, and Sandeep Sen. Fully dynamic maximal matching in o( (n)) update time. SIAM J. Comput. , 44(1):88--113, 2015. Announced at FOCS'11

    2015

  27. [35]

    Fully dynamic maximal matching in o( n) update time (corrected version)

    Surender Baswana, Manoj Gupta, and Sandeep Sen. Fully dynamic maximal matching in o( n) update time (corrected version). SIAM Journal on Computing , 47(3):617--650, 2018

    2018

  28. [36]

    Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing

    Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decremental reachability, scc, and shortest paths via directed expanders and congestion balancing. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS...

    2020

  29. [37]

    Exponentially faster massively parallel maximal matching

    Soheil Behnezhad, Mohammad Taghi Hajiaghayi, and David G Harris. Exponentially faster massively parallel maximal matching. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1637--1649. IEEE, 2019

    2019

  30. [38]

    Italiano

    Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. Deterministic fully dynamic data structures for vertex cover and matching. SIAM J. Comput. , 47(3):859--887, 2018

    2018

  31. [39]

    New deterministic approximation algorithms for fully dynamic matching

    Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. New deterministic approximation algorithms for fully dynamic matching. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA...

    2016

  32. [40]

    Fully dynamic approximate maximum matching and minimum vertex cover in O(log\( ^ 3 \) n) worst case update time

    Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. Fully dynamic approximate maximum matching and minimum vertex cover in O(log\( ^ 3 \) n) worst case update time. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algo...

    2017

  33. [41]

    Deterministically maintaining a (2 + ) -approximate minimum vertex cover in o(1/ ) amortized update time

    Sayan Bhattacharya and Janardhan Kulkarni. Deterministically maintaining a (2 + ) -approximate minimum vertex cover in o(1/ ) amortized update time. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego,...

    2019

  34. [42]

    Deterministic rounding of dynamic fractional matchings

    Sayan Bhattacharya and Peter Kiss. Deterministic rounding of dynamic fractional matchings. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Vi...

    2021

  35. [43]

    Incremental (1- ) -approximate dynamic matching in o(poly (1/ )) update time

    Joakim Blikstad and Peter Kiss. Incremental (1- ) -approximate dynamic matching in o(poly (1/ )) update time. arXiv preprint arXiv:2302.08432 , 2023

    2023 arXiv

  36. [44]

    Dynamic algorithms for packing-covering lps via multiplicative weight updates

    Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak. Dynamic algorithms for packing-covering lps via multiplicative weight updates. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1--47. SIAM, 2023

    2023

  37. [45]

    Sublinear algorithms for (1.5+ ) -approximate matching

    Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak. Sublinear algorithms for (1.5+ ) -approximate matching. In STOC , 2023

    2023

  38. [46]

    Dynamic matching with better-than-2 approximation in polylogarithmic update time

    Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, and David Wajc. Dynamic matching with better-than-2 approximation in polylogarithmic update time. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2...

    2023

  39. [47]

    Near-optimal dynamic rounding of fractional matchings in bipartite graphs

    Sayan Bhattacharya, Peter Kiss, Aaron Sidford, and David Wajc. Near-optimal dynamic rounding of fractional matchings in bipartite graphs. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, ...

    2024

  40. [48]

    Fully dynamic matching: Beating 2-approximation in ^ update time

    Soheil Behnezhad, Jakub a cki, and Vahab Mirrokni. Fully dynamic matching: Beating 2-approximation in ^ update time. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2492--2508, 2020

    2020

  41. [49]

    Fully dynamic ( + 1) coloring against adaptive adversaries

    Soheil Behnezhad, Rajmohan Rajaraman, and Omer Wasim. Fully dynamic ( + 1) coloring against adaptive adversaries. In Proceedings of the 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2025

    2025

  42. [50]

    Fully dynamic matching in bipartite graphs

    Aaron Bernstein and Cliff Stein. Fully dynamic matching in bipartite graphs. In Magnus M. Halldorsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015,...

    2015

  43. [51]

    Fully dynamic matching in bipartite graphs

    Aaron Bernstein and Cliff Stein. Fully dynamic matching in bipartite graphs. In International Colloquium on Automata, Languages, and Programming , pages 167--179. Springer, 2015

    2015

  44. [52]

    Faster fully dynamic matchings with small approximation ratios

    Aaron Bernstein and Cliff Stein. Faster fully dynamic matchings with small approximation ratios. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 , pages 692--7...

    2016

  45. [53]

    Faster fully dynamic matchings with small approximation ratios

    Aaron Bernstein and Cliff Stein. Faster fully dynamic matchings with small approximation ratios. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms , pages 692--711. SIAM, 2016

    2016

  46. [54]

    Simple dynamic spanners with near-optimal recourse against an adaptive adversary

    Sayan Bhattacharya, Thatchaphol Saranurak, and Pattara Sukprasert. Simple dynamic spanners with near-optimal recourse against an adaptive adversary. arXiv preprint arXiv:2207.04954 , 2022

    2022 arXiv

  47. [55]

    Fast dynamic cuts, distances and effective resistances via vertex sparsifiers

    Li Chen, Gramoz Goranci, Monika Henzinger, Richard Peng, and Thatchaphol Saranurak. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 1135--1146. IEEE, 2020

    2020

  48. [56]

    A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond

    Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , ...

    2020

  49. [57]

    Adaptive out-orientations with applications

    Aleksander BG Christiansen, Jacob Holm, Ivor van der Hoog, Eva Rotenberg, and Chris Schwiegelshohn. Adaptive out-orientations with applications. arXiv preprint arXiv:2209.14087 , 2022

    2022 arXiv

  50. [58]

    A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems

    Julia Chuzhoy and Sanjeev Khanna. A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 389--400, 2019

    2019

  51. [59]

    Maximum flow and minimum-cost flow in almost-linear time

    Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 612--623. IEEE, 2022

    2022

  52. [60]

    Round compression for parallel matching algorithms

    Artur Czumaj, Jakub a cki, Aleksander M a dry, Slobodan Mitrovi \'c , Krzysztof Onak, and Piotr Sankowski. Round compression for parallel matching algorithms. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 471--484, 2018

    2018

  53. [61]

    Fully dynamic almost-maximal matching: Breaking the polynomial worst-case time barrier

    Moses Charikar and Shay Solomon. Fully dynamic almost-maximal matching: Breaking the polynomial worst-case time barrier. In Ioannis Chatzigiannakis, Christos Kaklamanis, D \' a niel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and P...

    2018

  54. [62]

    Deterministic algorithms for decremental shortest paths via layered core decomposition

    Julia Chuzhoy and Thatchaphol Saranurak. Deterministic algorithms for decremental shortest paths via layered core decomposition. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2478--2496. SIAM, 2021

    2021

  55. [63]

    Entropy regularization and faster decremental matching in general graphs

    Jiale Chen, Aaron Sidford, and Ta-Wei Tu. Entropy regularization and faster decremental matching in general graphs. arXiv preprint arXiv:2312.09077 , 2023

    2023 arXiv

  56. [64]

    Fully dynamic maximal independent set in expected poly-log update time

    Shiri Chechik and Tianyi Zhang. Fully dynamic maximal independent set in expected poly-log update time. In Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS) , pages 370--381, 2019

    2019

  57. [65]

    A new deterministic algorithm for fully dynamic all-pairs shortest paths

    Julia Chuzhoy and Ruimin Zhang. A new deterministic algorithm for fully dynamic all-pairs shortest paths. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 1159--1172, 2023

    2023

  58. [66]

    On the hardness of partially dynamic graph problems and connections to diameter

    S ren Dahlgaard. On the hardness of partially dynamic graph problems and connections to diameter. In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP) , pages 48:1--48:14, 2016

    2016

  59. [67]

    A note on rounding matchings in general graphs

    Aditi Dudeja. A note on rounding matchings in general graphs. arXiv preprint arXiv:2402.03068 , 2024

    2024 arXiv

  60. [68]

    Deterministic simple (1+ ) -edge-coloring in near-linear time

    Michael Elkin and Ariel Khuzman. Deterministic simple (1+ ) -edge-coloring in near-linear time. arXiv preprint arXiv:2401.10538 , 2024

    2024 arXiv

  61. [69]

    Improved deterministic distributed matching via rounding

    Manuela Fischer. Improved deterministic distributed matching via rounding. Distributed Computing , 33(3):279--291, 2020

    2020

  62. [70]

    Improved massively parallel computation algorithms for mis, matching, and vertex cover

    Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovi \'c , and Ronitt Rubinfeld. Improved massively parallel computation algorithms for mis, matching, and vertex cover. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing , pages 129...

    2018

  63. [71]

    A time-optimal randomized parallel algorithm for mis

    Mohsen Ghaffari and Bernhard Haeupler. A time-optimal randomized parallel algorithm for mis. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2892--2903. SIAM, 2021

    2021

  64. [72]

    (1+ ) -approximate incremental matching in constant deterministic amortized time

    Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn, and Shay Solomon. (1+ ) -approximate incremental matching in constant deterministic amortized time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1886--1898. ...

    2019

  65. [73]

    Gabow, Takao Nishizeki, Oded Kariv, Daniel Leven, and Osamu Terada

    Harold N. Gabow, Takao Nishizeki, Oded Kariv, Daniel Leven, and Osamu Terada. Algorithms for edge-coloring. Technical Report 41/85, Tel Aviv University, 1985

    1985

  66. [74]

    Fully dynamic (1+ ) -approximate matchings

    Manoj Gupta and Richard Peng. Fully dynamic (1+ ) -approximate matchings. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA , pages 548--557. IEEE Computer Society, 2013

    2013

  67. [75]

    Maintaining approximate maximum matching in an incremental bipartite graph in polylogarithmic update time

    Manoj Gupta, Venkatesh Raman, and SP Suresh. Maintaining approximate maximum matching in an incremental bipartite graph in polylogarithmic update time. In Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS) , volume 29, pages 227--239, 2014

    2014

  68. [76]

    The expander hierarchy and its applications to dynamic graph algorithms

    Gramoz Goranci, Harald R \"a cke, Thatchaphol Saranurak, and Zihan Tan. The expander hierarchy and its applications to dynamic graph algorithms. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2212--2228. SIAM, 2021

    2021

  69. [77]

    Maintaining an edcs in general graphs: Simpler, density-sensitive and with worst-case time bounds

    Fabrizio Grandoni, Chris Schwiegelshohn, Shay Solomon, and Amitai Uzrad. Maintaining an edcs in general graphs: Simpler, density-sensitive and with worst-case time bounds. In Karl Bringmann and Timothy M. Chan, editors, 5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022...

    2022

  70. [78]

    Maintaining an edcs in general graphs: Simpler, density-sensitive and with worst-case time bounds

    Fabrizio Grandoni, Chris Schwiegelshohn, Shay Solomon, and Amitai Uzrad. Maintaining an edcs in general graphs: Simpler, density-sensitive and with worst-case time bounds. Proceedings of the 5th Symposium on Simplicity in Algorithms (SOSA) , pages 12--23, 2022

    2022

  71. [79]

    Parallel dynamic maximal matching

    Mohsen Ghaffari and Anton Trygub. Parallel dynamic maximal matching. In Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures , pages 427--437, 2024

    2024

  72. [80]

    Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation

    Mohsen Ghaffari and Jara Uitto. Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1636--1653. SIAM, 2019

    2019

  73. [81]

    Decremental sssp in weighted digraphs: Faster and against an adaptive adversary

    Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Decremental sssp in weighted digraphs: Faster and against an adaptive adversary. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2542--2561. SIAM, 2020

    2020

  74. [82]

    Deterministic algorithms for decremental approximate shortest paths: Faster and simpler

    Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Deterministic algorithms for decremental approximate shortest paths: Faster and simpler. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2522--2541. SIAM, 2020

    2020

  75. [83]

    Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

    Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM (JACM) , 48(4):723--760, 2001

    2001

  76. [84]

    Dynamic approximate all-pairs shortest paths: Breaking the o(mn) barrier and derandomization

    Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Dynamic approximate all-pairs shortest paths: Breaking the o(mn) barrier and derandomization. SIAM Journal on Computing , 45(3):947--1006, 2016

    2016

  77. [85]

    Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture

    Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-S...

    2015

  78. [86]

    A faster distributed algorithm for computing maximal matchings deterministically

    Micha Ha \'n \'c kowiak, Micha Karo \'n ski, and Alessandro Panconesi. A faster distributed algorithm for computing maximal matchings deterministically. In Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing , pages 219--228, 1999

    1999

  79. [87]

    On the distributed complexity of computing maximal matchings

    Michal Hanckowiak, Michal Karonski, and Alessandro Panconesi. On the distributed complexity of computing maximal matchings. SIAM Journal on Discrete Mathematics , 15(1):41--57, 2001

    2001

  80. [88]

    Dynamic deterministic constant-approximate distance oracles with n^ worst-case update time

    Bernhard Haeupler, Yaowei Long, and Thatchaphol Saranurak. Dynamic deterministic constant-approximate distance oracles with n^ worst-case update time. arXiv preprint arXiv:2402.18541 , 2024

    2024 arXiv

  81. [89]

    Constant-time dynamic ( \( \) +1)-coloring

    Monika Henzinger and Pan Peng. Constant-time dynamic ( \( \) +1)-coloring. ACM Trans. Algorithms , 18(2):16:1--16:21, 2022

    2022

  82. [90]

    A fast and simple randomized parallel algorithm for maximal matching

    Amos Israeli and Alon Itai. A fast and simple randomized parallel algorithm for maximal matching. Information Processing Letters , 22(2):77--80, 1986

    1986

  83. [91]

    Fully dynamic maintenance of vertex cover

    Zoran Ivkovic and Errol L Lloyd. Fully dynamic maintenance of vertex cover. In Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science , pages 99--111, 1993

    1993

  84. [92]

    An improved parallel algorithm for maximal matching

    Amos Israeli and Yossi Shiloach. An improved parallel algorithm for maximal matching. Information Processing Letters , 22(2):57--60, 1986

    1986

  85. [93]

    Regularized box-simplex games and dynamic decremental bipartite matching

    Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Regularized box-simplex games and dynamic decremental bipartite matching. In International Colloquium on Automata, Languages, and Programming (ICALP) , 2022

    2022

  86. [94]

    V. King. Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) , pages 81--89, 1999

    1999

  87. [95]

    Deterministic dynamic matching in worst-case update time

    Peter Kiss. Deterministic dynamic matching in worst-case update time. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA , volume 215 of LIPIcs , pages 94:1--94:21. Schloss Dagstuh...

    2022

  88. [96]

    A dynamic shortest paths toolbox: Low-congestion vertex sparsifiers and their applications

    Rasmus Kyng, Simon Meierhans, and Maximilian Probst Gutenberg. A dynamic shortest paths toolbox: Low-congestion vertex sparsifiers and their applications. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1174--1183, 2024

    2024

  89. [97]

    A fast parallel algorithm for the maximal independent set problem

    Richard M Karp and Avi Wigderson. A fast parallel algorithm for the maximal independent set problem. Journal of the ACM (JACM) , 32(4):762--773, 1985

    1985

  90. [98]

    Yang P. Liu. On approximate fully-dynamic matching and online matrix-vector multiplication. CoRR , abs/2403.02582, 2024

    2024 arXiv

  91. [99]

    Filtering: a method for solving graph problems in mapreduce

    Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: a method for solving graph problems in mapreduce. In Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures , pages 85--94, 2011

    2011

  92. [100]

    A simple parallel algorithm for the maximal independent set problem

    Michael Luby. A simple parallel algorithm for the maximal independent set problem. In Proceedings of the seventeenth annual ACM symposium on Theory of computing , pages 1--10, 1985

    1985

  93. [101]

    Simple deterministic algorithms for fully dynamic maximal matching

    Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. ACM Transactions on Algorithms (TALG) , 12(1):7, 2016

    2016

  94. [102]

    Dynamic spanning forest with worst-case update time: adaptive, las vegas, and O (n^ 1/2- ) -time

    Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, las vegas, and O (n^ 1/2- ) -time. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC) , pages 1122--1129, 2017

    2017

  95. [103]

    Dynamic minimum spanning forest with subpolynomial worst-case update time

    Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 950--961. IEEE, 2017

    2017

  96. [104]

    Beating the folklore algorithm for dynamic matching

    Mohammad Roghani, Amin Saberi, and David Wajc. Beating the folklore algorithm for dynamic matching. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS) , pages 111:1--111:23, 2022

    2022

  97. [105]

    Pseudorandom walks on regular digraphs and the rl vs

    Omer Reingold, Luca Trevisan, and Salil Vadhan. Pseudorandom walks on regular digraphs and the rl vs. l problem. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , pages 457--466, 2006

    2006

  98. [106]

    An on-line edge-deletion problem

    Yossi Shiloach and Shimon Even. An on-line edge-deletion problem. J. ACM , 28(1):1–4, jan 1981

    1981

  99. [107]

    Fully dynamic maximal matching in constant update time

    Shay Solomon. Fully dynamic maximal matching in constant update time. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA , pages 325--334. IEEE Computer Society, 2016

    2016

  100. [108]

    Fully dynamic maximal matching in constant update time

    Shay Solomon. Fully dynamic maximal matching in constant update time. In Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS) , pages 325--334, 2016

    2016

  101. [109]

    Open problem

    Shay Solomon. Open problem. Report from Dagstuhl Seminar 22461 Dynamic Graph Algorithms , page 62, 2022

    2022

  102. [110]

    A generalized matching reconfiguration problem

    Noam Solomon and Shay Solomon. A generalized matching reconfiguration problem. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference , volume 185 of LIPIcs , pages 57:1--57:20. Schloss Dagstuhl - ...

    2021

  103. [111]

    Metatheorems for dynamic weighted matching

    Daniel Stubbs and Virginia Vassilevska Williams . Metatheorems for dynamic weighted matching. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA , volume 67 of LIPIcs , pages 58:1--...

    2017

  104. [112]

    Faster maxflow via improved dynamic spectral vertex sparsifiers

    Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P Liu, Richard Peng, and Aaron Sidford. Faster maxflow via improved dynamic spectral vertex sparsifiers. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 543--556, 2022

    2022

  105. [113]

    Rounding dynamic matchings against an adaptive adversary

    David Wajc. Rounding dynamic matchings against an adaptive adversary. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA,...

    2020

  106. [114]

    Fully-dynamic minimum spanning forest with improved worst-case update time

    Christian Wulff-Nilsen. Fully-dynamic minimum spanning forest with improved worst-case update time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages 1130--1143, 2017

    2017

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.