Pith. sign in

REVIEW 1 major objections 3 minor 32 references

Semi-Streaming Matching in a Single Pass I: A New Framework for Lower Bounds via Blueprints

T0 review · 1 major / 3 minor · reviewed 2026-08-02 · deepseek-v4-flash

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

Pith's one-line read Any single-pass semi-streaming matching algorithm with approximation above 0.5585 needs n^{1+Ω(1/log log n)} space, the paper argues via a new blueprints framework.

desk verdict Blueprint framework is a genuine advance; the 0.558 bound is real if a repairable gap in Claim B.4 is fixed. read the letter →

arxiv 2607.14644 v1 pith:454ZE6M6 submitted 2026-07-16 cs.DS cs.CC

Sepehr Assadi , Max Jiang , Mars Xiang This is my paper · ORCID
classification cs.DScs.CC MSC 05C7068Q1768Q25
keywords semi-streamingalgorithmsmaximummatchinglowerboundsblueprintsRuzsa-Szemerédigraphscommunicationcomplexitysingle-passapproximationratio
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

In the semi-streaming model — one pass over the edge stream with roughly n·polylog n bits of memory — the maximum matching problem has a trivial greedy algorithm that achieves 0.5-approximation, and no algorithm has beaten it in decades. This paper tries to show that beating it is genuinely hard: it proves that any single-pass semi-streaming algorithm with approximation ratio better than (8−2√10)/3 ≈ 0.5585 on bipartite graphs requires n^{1+Ω(1/log log n)} space. The proof's main contribution is a framework that reduces the streaming lower bound to a finite combinatorial object called a blueprint; the lower bound improves with the 'value' of the best blueprint. The construction also recovers the previous best bound of about 0.590 with far simpler arguments. A sympathetic reader should care because the framework turns a long-stuck open question into a concrete, finite optimization problem: find better blueprints.

What carries the argument

The central object is the blueprint: a constant-size bipartite graph whose edges form a fractional matching and whose 'ban constraints' forbid both endpoints of certain vertex pairs from being matched. The carrying mechanism is an expansion: combine a blueprint with an extended Ruzsa-Szemerédi graph — a dense analogue of a Hamming graph whose edges are organized into many large matchings grouped by color — to generate a large bipartite graph with a hidden canonical matching. A lossy-compression lemma then shows that in this distribution any protocol that writes s bits can recover only O(s) special edges in expectation, so the matching the algorithm finds is small unless it spends too much sp

What would settle it

Exhibit a single-pass semi-streaming algorithm that, for all n-vertex bipartite graphs, outputs a matching of size at least ((8−2√10)/3+ε)·OPT using n^{1+o(1/log log n)} bits with high constant probability. A more contained check: instantiate Theorem 1 for a small constant C (say C=4) and δ=1/(100C) and verify that the claimed t=n^{Ω(1/log log n)} matching-groups of size n/C−δn satisfy the four ERS conditions; failure there would break the expansion lemma (Proposition 4.10) and the hard distribution.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that every single-pass semi-streaming lower bound for approximate matching can be derived from a finite 'blueprint': a constant-size bipartite graph with a fractional matching and ban constraints that encode which pairs of vertices cannot both be matched. The paper defines an expansion operation that combines a blueprint with a somewhat-dense extended Ruzsa-Szemerédi (ERS) graph to produce a hard input distribution, then proves an information-theoretic lemma showing that any low-space algorithm can find only few of the hidden 'special' edges. The best blueprint the authors construct has value (5−√10)/3, which translates to the approximation barrier

Load-bearing premise

The proof depends on Theorem 1's construction of somewhat-dense (C,r,t)-ERS graphs: for every constant C and small δ there must exist graphs with t=n^{Ω(1/log log n)} disjoint, induced matching-groups each of size n/C−δn. If that construction fails for the parameter regime used in Section 5.1, the expansion's canonical matching no longer has the size and hiddenness properties on which the lower bound rests.

Editorial extensions

If this is right

  • Any single-pass semi-streaming algorithm beating approximation ratio (8−2√10)/3 ≈ 0.5585 on bipartite graphs must use n^{1+Ω(1/log log n)} space; this raises the previous barrier from about 0.590.
  • The approximation barrier is tied to the best blueprint: a proper blueprint with value v yields a space lower bound for approximation α(v)=(2−2v)/(2−v), so improving the lower bound is exactly the same as increasing blueprint value.
  • The authors report that a companion work built on this framework to rule out any approximation strictly better than 1/2, which would make the greedy algorithm optimal; the present paper's own theorem is the 0.5585 bound.
  • With the same machinery, a small modification of Theorem 2 gives a lower bound of about 1.790 for streaming minimum vertex cover.
  • The older 2/3 and 0.590 lower bounds can be re-proven from blueprints with much shorter arguments, evidence that the new abstraction captures the source of hardness.

Reading between the lines

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

  • If the blueprint value V* is the right invariant, the open problem reduces to whether proper blueprints can achieve value approaching 2/3 (equivalently, approximation ratio approaching 1/2); reaching 2/3 would settle greedy optimality.
  • Because blueprints are constant-size, a computer search over small parameters is a plausible next test; the paper reports finding value ≈ 0.535 blueprints this way, so targeted enumeration may outrun the analytic construction before the framework hits its limit.
  • The modular split between blueprint, ERS host graph, and information-theoretic analysis suggests the same recipe may transfer to random-order streams or multi-pass algorithms by swapping the host graph, though the paper leaves those variants open.
  • The authors' own self-note that a companion paper already rules out anything better than 1/2 means this 0.5585 number is likely a step on the way; readers should weight the framework as the lasting contribution.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 3 minor

Summary. The paper develops a new framework for proving single-pass semi-streaming lower bounds for maximum matching. It introduces "blueprints" — constant-size labeled graphs with matching and ban constraints — and shows that any proper blueprint with approximation ratio α yields a streaming lower bound of roughly n^{1+Ω(1/log log n)} space for beating α-approximation. The framework uses a new family of "extended Ruzsa-Szemerédi (ERS) graphs" and an expansion operation that turns a blueprint plus an ERS graph into a hard communication instance. The authors then construct blueprints whose value implies the lower bound α > (8−2√10)/3 ≈ 0.558, improving the previous 0.590 bound. The main result is Theorem 4.

Significance. If the proof is completed, this is a significant contribution. The blueprint framework abstracts away the white-box RS-graph and information-theoretic machinery of prior lower bounds, reduces the lower-bound task to a constant-size combinatorial optimization problem, and already yields a new numerical bound. It also recovers the (2−√2) bound with a relatively short argument and suggests a concrete route toward settling whether 0.5-approximation is optimal. The modularity of the framework, the clean compression lemma (Proposition 2.2), and the black-box use of ERS graphs are genuine strengths. However, the paper currently contains a real gap in the proof of the ERS graph construction (Appendix B, Claim B.4), which is load-bearing for Theorem 1 and hence for the final lower bound. The gap appears readily repairable, but the printed proof is incomplete at that point.

major comments (1)
  1. [Appendix B, Claim B.4] The proof of the color-class density lower bound is incorrect as written. It says that because Q|p, "the last coordinate of a vector determines its weight_i(·) mod Q if the other coordinates are fixed". This is only true if d∈S_i; Claim B.1 does not guarantee that d is in every S_i, and when d∉S_i the last coordinate does not affect weight_i at all. The subsequent assertion that each residue occurs equally often among last coordinates is therefore unsupported. This bound feeds Claim B.5, hence the size guarantee r ≥ n/C − δn in Theorem 1, and in turn the canonical-matching size in Lemma 5.2 and the final n^{1+Ω(1/log log n)} lower bound. The gap appears repairable: since S_i is nonempty, choose k∈S_i and vary only that coordinate; because p is a multiple of Q, every residue mod Q occurs exactly p/Q times, so the density of each color class is exactly B/Q = 1/(C(1+10Cδ)) ≥ (1−10Cδ)/C. Ple
minor comments (3)
  1. [Appendix B, first paragraph] Theorem 1 is stated for every δ∈(0,1/(40C)), but the proof fixes δ with 1/δ an integer. As written, the construction does not cover all δ in the theorem statement; a standard rational-approximation or re-parameterization argument should be supplied.
  2. [§5.2, Lemma 5.4 proof] The sentence 'whenever Player(P+1) outputs an edge that does not belong to received messages and J, the protocol errs with probability at least δ/2' is not literally true for edges of the external matching E^{(P+1)}, which are deterministic functions of J and always present. The argument should be restricted to e∈E_base; this is sufficient because external edges are never special.
  3. [§5.2, Lemma 5.2 part 2] The sentence 'All edges of this subgraph ... are incident on vertices L\L(M⋆_base) and R\R(M⋆_base)' is imprecise; an edge from L(M⋆_base) to R\R(M⋆_base) is not incident on L\L(M⋆_base). The intended and sufficient statement is that every edge has at least one endpoint in (L\L(M⋆_base)) ∪ (R\R(M⋆_base)). Please rephrase.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the lower bound is a genuine reduction from blueprint value to streaming hardness; the only flagged issue is a repairable proof gap in Appendix B, not a circular step.

full rationale

The derivation chain is self-contained. Theorem 1 (ERS graphs) is proved in Appendix B by an explicit probabilistic construction (Claim B.1) and explicit weight/color definitions, not by assuming the target lower bound. Theorem 2 reduces streaming lower bounds to blueprint approximation values: the blueprint value α(G) is defined from fractional matching size before any lower bound is claimed, and the hard distribution instantiates the blueprint via an ERS host and proves by construction that large matchings have size ≈(2−value(G))|L| while matchings avoiding 'special' edges have size ≈(2−2·value(G))|L|. This yields exactly α(G)+δ — the ratio is derived, not fitted. Section 6's blueprint constructions are independent combinatorial gadgets; the constants 2−√2 and (8−2√10)/3 arise from the roots of quadratics in the amplification lemmas, and are not inserted into the construction. The only flagged concern is Claim B.4 in Appendix B: the printed 'last coordinate' argument requires d∈S_i, which Claim B.1 does not guarantee; however this is a localized proof gap (repairable because p is a multiple of Q and S_i is nonempty, making weight_i uniform mod Q), not a circular dependence of the conclusion on its inputs. The self-referential 'Follow up work' notice about the companion paper is not load-bearing for Theorem 4. Hence no circularity beyond a minor self-reference.

Assumptions & free parameters 3 free parameters · 5 assumptions · 2 invented entities

The central claim depends on the correctness of the ERS graph construction (Theorem 1), the communication-to-streaming reduction (Prop 2.1), and the information-theoretic compression bound (Prop 2.2). These are stated and proved in the paper, but not independently machine-checked.

free parameters (3)
  • δ (edge-deletion / slack parameter) = small constant, e.g., δ∈(0,1/(40C)); re-parameterized as δ←10Pδ
    Appears in ERS construction, hard distribution, and final lower bound; chosen arbitrarily small and not fitted to data.
  • ε (gadget scale in blueprint constructions) = ε = √2δ/4 (warm-up); ε = 2ηδ^3/√10 (main)
    Hand-chosen to make the value-increase inequalities in Claims 6.5 and 6.11 hold; no independent constraint.
  • K, t (recursion parameters in Lemma 6.6) = K=(1−value(G))·t, t≥1/6ε
    Integer parameters of the amplification gadget, chosen to make the blueprint proper and to satisfy the final inequality; not empirically fitted.
assumptions (5)
  • standard math One-way communication lower bounds transfer to streaming algorithms (Proposition 2.1).
    Standard reduction from streaming to communication games, cited to [AMS96] and used in Section 5 to derive Theorem 2.
  • standard math Yao's minimax principle; deterministic protocols are WLOG for distributional lower bounds.
    Invoked in Section 2.1 to assume deterministic protocols against a fixed distribution.
  • standard math Lossy compression entropy bound (Proposition 2.2).
    Proved in Appendix A using Shannon entropy; used to limit the number of special edges players can recover.
  • domain assumption Existence of ERS graphs with the parameters in Theorem 1.
    Proved in Appendix B by a probabilistic construction; the lower-bound framework treats it as a black-box input. If the construction has a flaw, the hard distribution in Section 5.1 fails.
  • standard math RS graph constructions of [FLN+02, GKK12] as inspiration/technique for ERS graphs.
    The ERS construction borrows techniques from prior RS graph work; not used as a black box, but relied on for the underlying method.
invented entities (2)
  • Blueprint
    purpose: Constant-size bipartite pattern whose value determines a semi-streaming matching lower bound; the central abstraction of the paper.
    Formal object defined in Section 4; its control over streaming lower bounds is proven internally (Theorem 2). It makes no empirical prediction outside the paper's own framework.
  • Extended RS (ERS) graph
    purpose: Somewhat-dense generalization of Hamming/RS graphs used to expand blueprints into hard instances.
    Defined in Section 3 and constructed in Appendix B; no external evidence beyond the paper's proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Semi-Streaming Matching in a Single Pass I: A New Framework for Lower Bounds via Blueprints." pith.science (2026). https://pith.science/paper/454ZE6M6

@misc{pith2026260714644,
  author       = {Pith},
  title        = {Pith review of: Semi-Streaming Matching in a Single Pass I: A New Framework for Lower Bounds via Blueprints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/454ZE6M6}},
  note         = {Machine review of arXiv:2607.14644}
}
abstract

In the semi-streaming model, we have an $n$-vertex graph $G=(V,E)$ whose edges arrive in an arbitrary order in a stream. The goal is to make one or a few passes over the stream, use a limited memory of $\tilde O(n)$ bits, and output a solution to the problem at hand at the end. A central open question in this area is to determine the best approximation ratio possible for the maximum matching problem via single-pass semi-streaming algorithms. This problem admits a simple $0.5$-approximation algorithm, by maintaining a maximal matching greedily, which, despite extensive efforts, has remained the state of the art. Lower bounds for this problem have also been few and far between with best known bounds ruling out better than $1/(1+\ln{(2)}) \sim 0.590$ approximation, using a highly complicated construction motivated by the literature on RS graphs from extremal graph theory. We develop a new framework for proving lower bounds for the semi-streaming matching problem. Our framework abstracts out the extremal graph theory and information theoretic arguments in the lower bounds, and reduces the problem to constructing certain constant-size graphs, which we call blueprints. Not only existing lower bounds can be captured by these blueprints, leading to far simpler and more concise arguments, but also we can design new blueprints that can be used to rule out $(8-2\sqrt{10})/3 \sim 0.558$-approximation for the semi-streaming matching problem. We believe this approach can be of its own independent interest and lead to further improvements on this tantalizing open question.

Figures

Figures reproduced from arXiv: 2607.14644 by the authors.

Figure 1
Figure 1. A high level illustration of a blueprint: existence of each edge (u, v) introduces a constraint between some pairs of vertices that forces at most one vertex per pair to have any edge. Here, the banned pairs of a single edge (u, v) are shown with dashed lines; only one endpoint of each dashed line has an edge. After the definition of these blueprints, the proof of our lower bound framework goes in three steps: • Ste… view at source ↗
Figure 2
Figure 2. An illustration a (4, r, t)-ERS graph and a single matching-group Mi inside it. We emphasize that in Definition 3.1 each matching-group Mi is not a matching but rather a union of C 2 disjoint matchings, and moreover—unlike Hamming graphs mentioned earlier—each Mi,x,y is not necessarily a perfect matching between Li,x and Ri,y. We also note that these ERS graphs are not Ruzsa-Szemer´edi graphs5 but satisfy the follow… view at source ↗
Figure 3
Figure 3. A simple blueprint with parameters P = 2 and C = 2. Solid (black) lines show the single edge in each blueprint and dashed (red) lines show the pairs of vertices banned by the edge. Finally, the following quantities determine how “good” a blueprint is for our purpose. Definition 4.3. Define the value of a blueprint G = (L, R, E,w) as: value(G) := 2 · P e∈E w(e) CP · P b∈[BL] ⃗sL(b) + P b ′∈[BR] ⃗sR(b ′) . For simpl… view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Examples of different proper blueprints, their edges (solid lines) and the pairs each edge bans (dashed lines). One can verify that all blueprints are maximal, namely, no other edge can be added to them without violating one of ban or matching constraints. 10 [PITH_FU…
Figure 5
Figure 5. Figure 5: An illustration of the graph G sampled from our hard distribution. A δ-fraction of edges in Gbase will be removed in the graph G. We emphasize that the choice of the graph Gers in the distribution is fixed and deterministic and is known to all players of the communicat…
Figure 6
Figure 6. Figure 6: The intuition behind the blueprint Gb in Lemma 6.2. Shaded (blue) vertices at the top are matched in G and the new shaded (red) vertices at the bottom are additionally matched in Gb. To show Gb is a proper blueprint, we need to ensure it satisfies constraints of Defini…
Figure 7
Figure 7. Figure 7: An intuitive explanation of the bans in the blueprint Gb of Lemma 6.2. The dashed edges depict the banned pairs. The ban constraint requires at most one endpoint of each dashed edge to be matched. Finally, we should calculate value(Gb) and compare it with value(G). By …
Figure 8
Figure 8. Figure 8: An illustration of the proper blueprint Gb in the proof of Lemma 6.2. The shaded (red) vertices at the bottom part are FreeL and FreeR. We start with setting up the parameters. Parameters of Gb. Define Pb = P + 1 , Cb = C , BbL = BbR = 2 , b⃗sL = b⃗sR = (1, s), where s…
Figure 9
Figure 9. Figure 9: An illustration of Gb in the proof of Lemma 6.6 and its various internal sets and their connections. Vertices of Gb. The choice of parameters fixes the vertices of Gb to also be Lb = Lb(1) ⊔ . . . ⊔ Lb(K+2) and Rb = Rb(1) ⊔ . . . ⊔ Rb(K+2) , where each of the blocks is…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 1 linked inside Pith

  1. [1]

    [A22] S. Assadi. A two-pass (conditional) lower bound for semi-streaming maximum matching. In J. S. Naor and N. Buchbinder, editors,Proceedings of the 2022 ACM-SIAM Sympo- sium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, V A, USA, January 9 - 12, 2022, pages 708–742. SIAM,

    2022

  2. [5]

    Assadi, S

    37 [ABK+25] S. Assadi, S. Behnezhad, C. Konrad, K. K. Naidu, and J. Sundaresan. Settling the pass complexity of approximate matchings in dynamic graph streams. In Y. Azar and D. Panigrahi, editors,Proceedings of the 2025 Annual ACM-SIAM Symposium on 38 Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 864–904. SIAM,

    2025

  3. [6]

    Assadi, S

    1, 37 [ABKL23] S. Assadi, S. Behnezhad, S. Khanna, and H. Li. On regularity lemma and barriers in streaming and dynamic matching. In B. Saha and R. 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

  4. [8]

    7 [AG11] K. J. Ahn and S. Guha. Linear programming in the semi-streaming model with appli- cation to the maximum matching problem. InAutomata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II, pages 526–538,

    2011

  5. [12]

    Assadi, J

    1, 37 [ASY26] S. Assadi, J. Sundaresan, and H. Yazdanyar. Coloring graphs with few colors in the streaming model. InProceedings of the 2026 Annual ACM-SIAM Symposium on Dis- crete Algorithms, SODA 2026.To appear; available as arXiv preprint arXiv:2510.18177. SIAM,

    arXiv 2026

  6. [14]

    Behnezhad and S

    7 [BK22] S. Behnezhad and S. Khanna. New trade-offs for fully dynamic matching via hierarchical EDCS. In J. S. Naor and N. Buchbinder, editors,Proceedings of the 2022 ACM-SIAM 39 Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, V A, USA, January 9 - 12, 2022, pages 3529–3566. SIAM,

    2022

  7. [16]

    Epstein, A

    37 [ELSW13] L. Epstein, A. Levin, D. Segev, and O. Weimann. Improved bounds for online pre- emptive matching. In N. Portier and T. Wilke, editors,30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany, volume 20 ofLIPIcs, pages 389–399. Schloss Dagstuhl - Leibniz- Zentrum f¨ ur Informatik,

    2013

  8. [19]

    1 [GKK12] A. Goel, M. Kapralov, and S. Khanna. On the communication and streaming complexity of maximum bipartite matching. In Y. Rabani, editor,Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 468–485. SIAM,

    2012

Show all 32 references
  1. [21]

    Kapralov

    3 [Kap13] M. Kapralov. Better bounds for matchings in the streaming model. InProceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1679–1697,

    2013

  2. [23]

    Konrad, F

    1, 2, 3, 22, 36 [KMM12] C. Konrad, F. Magniez, and C. Mathieu. Maximum matching in semi-streaming with few passes. In A. Gupta, K. Jansen, J. D. P. Rolim, and R. A. Servedio, editors,Approxi- mation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15...

    2012

  3. [24]

    Konrad and K

    1 [KN21] C. Konrad and K. K. Naidu. On two-pass streaming algorithms for maximum bipartite matching. In M. Wootters and L. Sanit` a, editors,Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, August 16-18, 2021, Univers...

    2021

  4. [25]

    Konrad and K

    7 [KN24] C. Konrad and K. K. Naidu. An unconditional lower bound for two-pass streaming al- gorithms for maximum matching approximation. In D. P. Woodruff, editor,Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, V A, USA, January 7-10, ...

    2024

  5. [26]

    1, 37 [KVV90] R. M. Karp, U. V. Vazirani, and V. V. Vazirani. An optimal algorithm for on-line bi- partite matching. In H. Ortiz, editor,Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 352–358. ACM,

    1990

  6. [28]

    McGregor

    36 [McG05] A. McGregor. Finding graph matchings in data streams. InApproximation, Ran- domization and Combinatorial Optimization, Algorithms and Techniques, 8th Interna- tional Workshop on Approximation Algorithms for Combinatorial Optimization Prob- lems, APPROX 2005 and 9th ...

    2005

  7. [29]

    1 [Pra25] K. Pratt. A note on ordered ruzsa-szemer´ edi graphs.CoRR, abs/2502.02455,

    arXiv

  8. [30]

    Paz and G

    7 [PS17] A. Paz and G. Schwartzman. A (2 +ϵ)-approximation for maximum weight matching in the semi-streaming model. In P. N. Klein, editor,Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January ...

    2017

  9. [31]

    1 [PSW25] E. Pyne, N. S. Sheffield, and W. Wang. Catalytic communication. In R. Meka, editor, 16th Innovations in Theoretical Computer Science Conference, ITCS 2025, January 41 7-10, 2025, Columbia University, New York, NY, USA, volume 325 ofLIPIcs, pages 79:1–79:24. Schloss D...

    2025

  10. [1990]

    Lee and S

    1 [LS17] E. Lee and S. Singla. Maximum matching in the online batch-arrival model. In F. Eisen- brand and J. K¨ onemann, editors,Integer Programming and Combinatorial Optimiza- tion - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings...

    2017

  11. [1996]

    Assadi and J

    4 [AS23] S. Assadi and J. Sundaresan. Hidden permutations to the rescue: Multi-pass streaming lower bounds for approximate matchings. In64th IEEE Annual Symposium on Foun- dations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 909–932. IEEE,

    2023

  12. [2002]

    Fischer, S

    1, 2, 3, 6, 7 [FMU22] M. Fischer, S. Mitrovic, and J. Uitto. Deterministic (1 +ϵ)-approximate maximum matching with poly(1/ϵ) passes in the semi-streaming model and beyond. In S. Leonardi and A. Gupta, editors,STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, ...

    2022

  13. [2003]

    2 [RS78] I

    URLhttps://hdl.handle.net/ 1721.1/28274. 2 [RS78] I. Z. Ruzsa and E. Szemer´ edi. Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai, 18:939–945,

    1976

  14. [2005]

    Fischer, E

    1 [FLN+02] E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, and A. Samorod- nitsky. Monotonicity testing over general poset domains. In J. H. Reif, editor,Pro- ceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montr´ eal, Qu´ ebec,...

    2002

  15. [2006]

    Derakhshan, A

    43 [DGR25] M. Derakhshan, A. Ghasemi, and R. Rajaraman. One-way communication complexity of minimum vertex cover in general graphs. In K. Censor-Hillel, F. Grandoni, J. Ouaknine, and G. Puppis, editors,52nd International Colloquium on Automata, Languages, and Programming, ICAL...

    2025

  16. [2011]

    Assadi, S

    1 [AKL17] S. Assadi, S. Khanna, and Y. Li. On estimating maximum matching size in graph streams. InProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Dis- crete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1723–1742,

    2017

  17. [2012]

    Huang, B

    1, 2, 3, 6, 7, 10, 37 [HPT+19] Z. Huang, B. Peng, Z. G. Tang, R. Tao, X. Wu, and Y. Zhang. Tight competitive ratios of classic matching algorithms in the fully online model. In T. M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, S...

    2019

  18. [2013]

    Kapralov

    1, 2, 3 40 [Kap21] M. Kapralov. Space lower bounds for approximating maximum matching in the edge arrival model. In D. Marx, editor,Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1874–1893. SIAM,

    2021

  19. [2017]

    Assadi, C

    1 [AKNS24] S. Assadi, C. Konrad, K. K. Naidu, and J. Sundaresan.O(log logn) passes is optimal for semi-streaming maximal independent set. In B. Mohar, I. Shinkar, and R. O’Donnell, editors,Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouve...

    2024

  20. [2019]

    Assadi and S

    37 [AB21a] S. Assadi and S. Behnezhad. Beating two-thirds for random-order streaming match- ing. In N. Bansal, E. Merelli, and J. Worrell, editors,48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glas- gow, Scotland (Virtual ...

    2021

  21. [2021]

    Assadi and S

    1, 37 [AB21b] S. Assadi and S. Behnezhad. On the robust communication complexity of bipartite matching. In M. Wootters and L. Sanit` a, editors,Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, August 16-18, 2021, Univ...

    2021

  22. [2023]

    Assadi, A

    1 [ABL+25] S. Assadi, A. Bernstein, Z. Langley, L. C. Lau, and R. Wang. Streaming and com- munication complexity of load-balancing via matching contractors. In Y. Azar and D. Panigrahi, editors,Proceedings of the 2025 Annual ACM-SIAM Symposium on Dis- crete Algorithms, SODA 20...

    2025

  23. [2024]

    Behnezhad and A

    1 [BG24] S. Behnezhad and A. Ghafari. Fully dynamic matching and ordered ruzsa-szemer´ edi graphs. In65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 314–327. IEEE,

    2024

  24. [2025]

    Assadi and A

    1 [AB19] S. Assadi and A. Bernstein. Towards a unified theory of sparsification for matching problems. In J. T. Fineman and M. Mitzenmacher, editors,2nd Symposium on Sim- plicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA, volume 69 ofOASIcs, pages 11:1–11...

    2019

Pith tools

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