PaperlayerView exact revision on arXiv

Source-linked AI summary

An Unconditional Space-Approximation Lower Bound for Semi-Streaming Matching

Yang P. Liu, Kheeran Naidu, Hoai-An Nguyen, Janani Sundaresan

arXiv:2610.36577v1cs.DS

TL;DR

The paper proves an unconditional p-pass lower bound matching the conditional result of: no p-pass semi-streaming algorithm can output a better than (1−3⁻ᵖ+δ)-approximate maximum bipartite matching. The paper gives two proofs using Ruzsa-Szemerédi hierarchies and induced communication lower bounds, including a direct inductive communication argument. For any sufficiently small constant ε > 0, a (1−ε)-approximation requires Ω(log(1/ε)) passes.

  • Problem

    The paper proves an unconditional p-pass lower bound matching the conditional result of: no p-pass semi-streaming algorithm can output a better than (1−3⁻ᵖ+δ)-approximate maximum bipartite matching.

    Source: §1 · p. 3

  • Method

    The paper gives two proofs using Ruzsa-Szemerédi hierarchies and induced communication lower bounds, including a direct inductive communication argument.

    Source: §3.1 · p. 8, §3.2 · p. 8, §6.2 · p. 34

  • Results

    For any sufficiently small constant ε > 0, a (1−ε)-approximation requires Ω(log(1/ε)) passes.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The result gives an unconditional lower bound matching the conditional pass–approximation result of, for algorithms that output matching edges rather than estimate matching size.

    Source: §1 · p. 3

    The stated reduction considers randomized constant-error algorithms that output a valid matching on every run.

    Source: §7.5 · p. 48

Abstract

from arXiv · show

We prove the first unconditional lower bound tradeoff between the number of passes and the approximation factor of maximum matchings in the semi-streaming model. Specifically, we show that any algorithm that outputs an $(1-\varepsilon)$-approximation to maximum matching requires $\Omega(\log(1/\varepsilon))$ passes for constant $\varepsilon \in (0,1)$. Prior to our result, such tradeoffs were proven only conditioned on a certain combinatorial assumption about the density of Ruzsa-Szemer\'edi graphs. The state-of-the-art unconditional lower bound rules out any approximation factor better than $(8/9)$ in two passes but leaves open the possibility of a $(1-\varepsilon)$-approximation for any $\varepsilon > 0$ even in three passes. We provide two different proofs of our result: the first proof uses the recent hierarchical-embedding framework of Assadi, Konrad, Naidu, and Sundaresan (STOC 2024) along with combinatorial constructions using Ruzsa-Szemer\'edi graphs. The second extends the two-level Ruzsa-Szemer\'edi hierarchy of Konrad and Naidu (SODA 2024) beyond two levels and proves the corresponding communication lower bound directly by induction, rather than through a reduction to Index.

1 Introduction

The paper asks how many passes semi-streaming algorithms need to output an approximate maximum bipartite matching. It proves an unconditional pass–approximation tradeoff, matching a previously conditional lower bound while studying edge output rather than matching-size estimation.

1 Introduction

  • The paper studies insertion-only bipartite edge streams in the semi-streaming regime, with near-linear eO(n) memory and an output matching rather than a size estimate.The question is how many passes are needed for a (1−ε)-approximation when ε is constant.Source: §1 · p. 3
  • Existing semi-streaming upper bounds use O(1/ε²) passes or O((log n)/ε) passes, while multipass lower-bound progress had been more limited.The paper also situates its contribution among work on other graph problems and dynamic-stream matching.Source: §1 · pp. 3–4
  • Prior lower bounds gave an Ω(log(1/ε)/log(1/β_n)) pass requirement, with β_n tied to Ruzsa-Szemerédi graph density.For the known β_n ≥ 1/log log n bound, this did not imply a constant-ε lower bound; assuming β_n = Ω(1) would yield Ω(log(1/ε)) passes.Source: §1 · p. 3
  • For any sufficiently small constant ε > 0, a (1−ε)-approximation requires Ω(log(1/ε)) passes.The result is unconditional and concerns algorithms that output matching edges.Source: §1 · p. 3
  • The result matches the conditional bound of, but unlike it addresses outputting matching edges rather than estimating matching size.Both proofs use Ruzsa-Szemerédi graph hierarchies and their induced communication/search problems.Source: §1 · p. 3

2 Preliminaries

The preliminaries define the graph family and embedding operation used in the proofs, alongside notation for graph quantities and asymptotic parameters.

2 Preliminaries

  • Logarithms are base 2 unless otherwise stated, and tilde asymptotic notation suppresses logarithmic factors in relevant size parameters.The preliminaries also define tuple-prefix notation, binary entropy, Hamming distance, and distribution notation.Source: §2 · p. 4
  • For a graph G, μ(G) denotes maximum matching size; G[U] denotes the subgraph induced by U.Source: §2 · p. 4
  • An (r,t)-RS graph partitions its edges into t pairwise edge-disjoint induced matchings, each of size r.Each matching is induced with respect to the whole graph: its endpoints contain no other graph edges.Source: §2 · p. 4
  • The RS-graph construction supplies parameters with t ≥ n^{c_rs}/log log n for sufficiently large n.The constant c_rs depends on the chosen sufficiently small constant δ_rs.Source: §2 · pp. 4–5
  • Embedding a family of inner bipartite graphs into an outer RS graph replaces each outer edge with a copy of its corresponding inner graph.The copy's endpoints are paired with the endpoints of that outer edge.Source: §2 · p. 5

3 Technical Overview

Prior work used Ruzsa-Szemerédi graphs to establish one- and two-pass matching lower bounds, but the two-pass information-theoretic argument did not extend to more passes. The paper develops two proof approaches for its multipass lower bound.

3.1 Prior Work

  • [GKK12] showed that beating 2/3 requires finding an Ω(ε)-fraction of the hidden special induced matching, forcing Ω(rt) = Ω(n^{1+1/log log n}) space.Their instance independently removes each RS-graph edge with probability 1/2 and reveals auxiliary edges only after the RS-graph edges.Source: §3.1 · pp. 5–6
  • The two-pass construction layers hard instances, so the algorithm must contend with an unknown outer special matching and unknown inner special matchings.[KN24] argues that either learning about many smaller instances early or solving them later requires more than semi-streaming space.Source: §3.1 · p. 7
  • [KN24] established a two-pass lower bound ruling out approximation ratios above 8/9 in semi-streaming space.Its construction nests one-pass hard instances inside a two-level RS-graph hierarchy; the special outer matching is revealed after the first pass.Source: §3.1 · pp. 6–7
  • [KN24]’s approach did not extend beyond two passes because its information-theoretic component relied on two-way Index communication tradeoffs.The paper extends the hierarchy to p passes, yielding the stated barrier against ratios better than 1−1/3^p and hence an Ω(log(1/ε))-pass requirement.Source: §3.1 · p. 8

3.2 Our Approach

  • The first approach applies the hierarchical-embedding framework of to groups of smaller (p−1)-pass instances, with the special group revealed only after the first pass.The argument balances gaining advantage across all r·t instances early against solving the selected group later, using the smaller-instance space bound.Source: §3.2 · p. 8
  • The first approach adapts round elimination so identifying a special induced matching, and solving only a large constant fraction of its instances, suffices.This corresponds to a large matching identifying many special edges without requiring every special edge.Source: §3.2 · p. 8
  • The second approach proves the communication lower bound directly by induction rather than reducing it to Index.Its p+1-player problem uses hidden indices to select entries from a table, and the induction tracks information about the final output vector.Source: §3.2 · pp. 8–9
  • With p passes, the direct communication argument bounds the best natural strategy by the cost of choosing a level and paying for its hidden possibilities.At level k, that cost is roughly r1· · · rk tk; the lower bound is optimal up to logarithmic factors.Source: §3.2 · p. 9

4 First Proof: Hierarchical Embeddings

The first proof establishes the semi-streaming lower bound by reducing it to a communication lower bound using recursively defined hard matching distributions built from Ruzsa–Szemerédi graph embeddings. It turns near-perfect matchings into a search problem over hidden ultimate gadgets and applies round elimination.

First Proof: Hierarchical Embeddings

  • Theorem 2 gives a communication-cost lower bound for p-round, (p + 1)-player protocols that output an (1 − ε)-approximate maximum matching with at least 2/3 success probability.It is stated for p ∈ N, 0 < ε ≤ 1, and sufficiently large n; the extracted passages omit the bound's full expression.Source: §4 · p. 9
  • The proof converts a p-pass, eO(n)-space semi-streaming algorithm into a communication protocol and uses the communication lower bound to rule out its space use for the stated approximation regime.The protocol is required to succeed with probability at least 2/3; the supplied passages do not expose the full quantitative bound.Source: §4 · pp. 9–10
  • In the embedding product, each outer induced matching yields a vertex-disjoint union of its corresponding inner graphs, with no additional edges on those vertices.This property relies on the outer Ruzsa–Szemerédi matchings being induced and edge-disjoint.Source: §4 · pp. 10–11
  • For p ≥ 1, the hard distribution Gp embeds many independent instances from Gp−1 into an outer Ruzsa–Szemerédi graph and gives an auxiliary matching to the final player.The base distribution G0 consists of parallel-or-cross gadgets, each with a perfect matching, while recursive instances contain nested special subgraphs and ultimate gadgets.Source: §4 · pp. 11–13
  • The recursive instances have product-distributed player inputs, a perfect matching, and an ultimate induced matching of size (κrs)^p · n.The construction also bounds a vertex cover in the subgraph induced by vertices outside the ultimate matching.Source: §4 · pp. 13–15

Matching structure

  • Any (1−ε)-approximate matching of G ∼ Gp contains at least a (1−ε/(κ_rs)^p) fraction of the edges of the ultimate matching M⋆.This follows because G has a perfect matching of size n, while a matching avoiding M⋆ is bounded by a vertex cover.Source: §4 · p. 16

Search reduction

  • An s-communication matching protocol can be augmented into a protocol solving the hidden search predicate with communication cost s + O(n log n).The augmentation records auxiliary matching edges so the transcript identifies which edges belong to ultimate gadgets.Source: §4 · pp. 16–17

Round-elimination induction

  • Round elimination removes the first round and final player while retaining sufficient success, and induction reaches a zero-round protocol that cannot beat random guessing.The proof establishes the base case and inductive step for deterministic protocols, then invokes Yao’s minimax principle for randomized protocols.Source: §4 · pp. 18–19

Communication lower bound

  • For p = o(log log n / log log log n), the proof derives CC(π) = s = n^(1+Ω(1/(log log n)^3p)).The argument sets ε = (κ_rs)^p − ρ for a positive constant ρ.Source: §4 · pp. 20–21

5 Round Elimination of Hierarchical Embedding

The section develops a round-elimination argument that reduces a p-round, (p + 1)-player protocol to a (p − 1)-round, p-player protocol while controlling success loss through simulated input distributions. It then derandomizes the public-coin protocol by fixing a favorable public random string, preserving its guarantees.

5 Round Elimination of Hierarchical Embedding

  • The lemma's round-elimination argument converts any deterministic p-round, (p + 1)-player protocol for Pp into a deterministic (p − 1)-round, p-player protocol for Pp−1.The resulting protocol is evaluated on a uniform random search sequence; the stated lemma also allows parameters η and δ in (0,1].Source: §5 · p. 21, Step 2: Round Elimination · p. 27

Step 1: Player Elimination

  • Player elimination simulates the removed player using public knowledge, preserving success probability δ while reducing information cost.The induced instance distribution matches Gp; a transcript-compression step then gives a low-communication protocol, and truncation reduces success by at most η.Source: Step 1: Player Elimination · pp. 22, 23, 25

Step 2: Round Elimination

  • The transformation yields a (p − 1)-round, p-player protocol for Pp−1 with success probability at least δ −η − s/(2 · rp · tp).The new protocol simulates the original protocol after sampling its first-round messages; its input distribution differs from the player-elimination protocol's distribution.Source: Step 2: Round Elimination · pp. 25, 27
  • Because communication cost is measured in the worst case, averaging lets the protocol fix a public random string that preserves πp−1’s guarantees.Source: Step 2: Round Elimination · p. 28

6 Second Proof: A Direct Communication Lower Bound

This section presents the second proof, establishing a communication lower bound directly by induction over levels in the one-way HiddenRestrictions game. It tracks information about selected table restrictions as hidden indices are revealed, using an invariant across critical points to relate the final output vector to information in the transcript.

6 Second Proof: A Direct Communication Lower Bound

  • Theorem 3 considers any randomized p-pass one-way protocol for HiddenRestrictions, with communication cost b = CC(P), parameters t_i ≥ 2 and r_i ≥ 1, and fixed 0 < η < 1/2; it takes t_{p+1} = 2.Source: §6 · p. 29

6.1 Information Bounds for Restrictions

  • Information bounds for restrictions use KL divergence to control how much a transcript can reveal about a table after a selector chooses one column per row.The section develops bounds by decomposing divergence across table entries and comparing selected restrictions with the full table and selector distributions.Source: §6.1 · pp. 29–32

6.2 Inductive Proof of Theorem 3

  • The induction fixes protocol randomness to obtain a deterministic protocol with the same communication and expected Hamming-error guarantee under DHR.The proof grants critical players free reveals, strengthening the protocol, and uses transcript points after their messages to track when hidden indices become available.Source: §6.2 · pp. 33–34
  • Under the product distribution DHR, conditioning on a transcript prefix and free reveals preserves independence among the players’ inputs, supporting the inductive transcript analysis.The proof establishes this by showing that each deterministic message or free reveal restricts only its sender’s input, leaving the consistent input set a product rectangle.Source: §6.2 · pp. 33–34
  • Under DHR, the output bits are independent uniform bits from f1, and the transcript’s information about them is related to expected Hamming error.Source: §6.2 · p. 35
  • Conditioning on the prior transcript and free reveals isolates the selected table; once G_k is fixed, the critical player’s remaining input contributes no extra information.Source: §6.2 · p. 37
  • At each critical point, the proof propagates Ψ_k ≤ Φ_k using Lemma 6.4 and bounds information in the pre-point transcript by its b-bit length.Source: §6.2 · pp. 38–39
  • Figure 7 shows each hidden index selecting an induced matching whose edges carry child blocks, with the recursion ending in a possible edge determined by a randomized rule.Source: Figure 7 · p. 40

7 From Communication to Streaming

The section connects approximate bipartite matching to HiddenRestrictions using Ruzsa–Szemerédi graphs, relating large matchings to predictions of hidden output bits. It then turns a streaming algorithm into a low-communication protocol and uses the resulting decoding advantage to derive a superlinear space lower bound.

7.1 The Hierarchical Graph

  • The reduction encodes HiddenRestrictions output bits in a bipartite graph built from Ruzsa–Szemerédi graphs, where a large matching reveals information about the hidden bits.The construction uses a depth-p hierarchy of RS-graph replacements: selected matchings follow the hidden indices, while active leaves correspond to output-coordinate tuples and their edges are randomly masked and deleted.Source: §7 · p. 40, §7.1 · pp. 40–41

7.2 Matching Structure

  • The active leaf edges form an induced matching, and the constructed matching exceeds the maximum matching after deleting all possible active leaf edges by exactly the number of present active leaf edges.There is one possible active leaf edge for each of the r1 ··· rp output-coordinate tuples.Source: §7.2 · p. 42

7.3 Decoding from a Large Matching

  • With high probability, every (1 − 3^-p + ε)-approximate matching contains at least cp,εN1 active leaf edges, enabling a decoder to predict corresponding masked output bits with advantage.The decoder selects a fixed-size random subset of returned active leaf edges and guesses 1 for their masked bits; a coupling argument preserves the bias even when the matching depends on the full edge stream.Source: §7.3 · pp. 45–46
  • For each selected active-leaf edge, the decoder’s gain over a fair guess is q/[2(2−q)], yielding total advantage proportional to E[|S|].The decoder uses an independent fair bit when the leaf edge is not in the matching.Source: §7.3 · p. 47

7.4 Simulating the Streaming Algorithm

  • The streaming simulation gives a p-round HiddenRestrictions protocol with charged communication O(p sA), using memory states rather than transmitted edge lists.The protocol also uses p free input reveals, but neither f1 nor the deletion coins are revealed, and the streaming algorithm itself sees only the edge stream and its random bits.Source: §7.4 · pp. 47–48

7.5 Parameter Choice and Proof

  • The parameter choice yields a space lower bound of N^{1+Ω_{p,ε}((log log n)^−p)} for constant-error p-pass (1−3^−p+ε)-approximation algorithms.The algorithm is assumed to output a valid matching on every run; the construction sets N = Θ_{p,ε}(n) and L = Θ(log log n).Source: §7.5 · pp. 48, 50

A.1 Information Theory

This appendix introduces information-theoretic notation used throughout the paper, defining entropy, conditional entropy, mutual information, and conditional mutual information.

A.1 Information Theory

  • The appendix collects information-theoretic notation and standard facts used throughout the paper.It refers readers to Cover and Thomas for background and proofs.Source: §A.1 · p. 54
  • Entropy is introduced as a measure for a random variable, with its defining expression given in equation (15).The displayed expression sums probability-weighted logarithms over outcomes.Source: §A.1 · p. 54
  • Conditional entropy is defined as the expectation of entropy under the distribution of the conditioning variable.The text also specifies that the conditional entropy is computed from the distribution of A given B = B.Source: §A.1 · p. 54
  • Mutual information is defined by equivalent entropy differences, while conditional mutual information is introduced separately.The mutual information identity is I(A ; B) := H(A) − H(A | B) = H(B) − H(B | A).Source: §A.1 · p. 54

A.1.1 Entropy and Mutual Information

This subsection states basic entropy and mutual-information properties used throughout the paper. It also gives a conditioning result for mutual information when A and D are conditionally independent given C.

A.1.1 Entropy and Mutual Information

  • The subsection collects basic entropy and mutual-information properties used throughout the paper.These include entropy bounds, nonnegativity, conditioning, the chain rule, and data processing.Source: §A.1.1 · p. 55
  • Entropy is bounded between zero and the logarithm of the support size, with equality at the upper bound exactly for a uniform distribution.The stated bound is 0 ≤ H(A) ≤ log |supp(A)|.Source: §A.1.1 · p. 55
  • Mutual information is nonnegative, and conditional entropy cannot increase when conditioning on an additional variable.The text gives equality conditions for both properties: conditional independence for mutual information, and A ⊥ C | B for the entropy inequality.Source: §A.1.1 · p. 55
  • The subsection states the chain rule and data processing inequality, including that applying a function to A cannot increase its conditional mutual information with B given C.The displayed inequality is I(f(A) ; B | C) ≤ I(A ; B | C).Source: §A.1.1 · p. 55
  • If A and D are independent conditioned on C, then conditioning on D cannot decrease the mutual information between A and B given C.The proposition states I(A ; B | C) ≤ I(A ; B | C, D).Source: §A.1.1 · p. 55

A.1.2 Distances Between Distributions

This subsection introduces distances between distributions, including Kullback–Leibler divergence and total variation distance, and lists several associated facts.

A.1.2 Distances Between Distributions

  • Kullback–Leibler divergence is defined for two distributions on the same finite set, with conventions for zero-probability terms and infinite divergence.Terms with μ(a) = 0 contribute zero; divergence is infinite if μ(a) > 0 while ν(a) = 0 for some a.Source: §A.1.2 · p. 55
  • The subsection states Fact A.3 in terms of divergence between conditional distributions and a distribution conditioned only on C.The excerpt gives the distributions being compared but not the complete displayed relation.Source: §A.1.2 · p. 55
  • Total variation distance is introduced for two distributions on the same finite set, followed by Facts A.4–A.6, including Pinsker’s inequality.The excerpt also notes that conditional distributions under ν may be chosen arbitrarily on zero-probability prefixes.Source: §A.1.2 · p. 56

A.2 Streaming and Communication

This section defines the streaming and communication settings and shows how a p-pass, s-space streaming algorithm can be simulated by a multi-party protocol with at most pks bits of communication.

A.2 Streaming and Communication

  • A p-pass streaming algorithm reads the same insertion-only edge stream p times and must output a valid matching whose size is at least αµ(G) to succeed.For randomized algorithms, success means probability at least 1/2 + ζ on every input, for a fixed constant ζ > 0.Source: §A.2 · p. 56
  • In the communication model, k players speak in order over a public blackboard, and communication cost is the worst-case total bits sent across rounds and randomness.Protocols may use public and private randomness; transcripts are padded to a common worst-case length when needed.Source: §A.2 · p. 56
  • A p-pass s-space streaming algorithm on a stream partitioned among k players yields a p-round protocol costing at most pks bits, with the last player producing the output.The streaming output is not charged unless it must be written on the blackboard, in which case its encoding length is added.Source: §A.2 · p. 56
  • The simulation passes the streaming memory state from player to player, using at most ks bits per pass and preserving the algorithm’s success probability.Thus communication lower bounds can be translated into streaming lower bounds.Source: §A.2 · pp. 56–57

A.3 Information Cost and Message Compression

This section introduces external information cost as a measure of what the transcript reveals about the input and uses message compression to relate sampling communication to KL-divergence.

A.3 Information Cost and Message Compression

  • External information cost measures how much the charged transcript reveals about the entire input to an outside observer.The definition uses the input X, charged transcript Π, and public randomness R.Source: §A.3 · p. 57
  • For any protocol, external information cost is bounded by its worst-case communication cost.The section derives this result from information-theoretic definitions and padded transcripts.Source: §A.3 · p. 57
  • Alice can sample exactly from A when Bob knows only B by sending one public-randomness-assisted message with expected length D(A || B) + 2 log(1 + D(A || B)) + O(1).This message-compression result is attributed to, strengthened in, and presented from.Source: §A.3 · p. 57
  • The exposition uses a weaker KL-divergence bound, replacing the logarithmic overhead by a constant-factor term for some absolute constant ccomp ≥ 1.The stated simplification is D(A || B) + 2 log(1 + D(A || B)) + O(1) ≤ D(A || B) + 10D(A || B) + O(1).Source: §A.3 · p. 57

A.4 Graph Facts

The section records König’s theorem for bipartite graphs: maximum matching size equals minimum vertex-cover size.

A.4 Graph Facts

  • In every bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.This is König’s theorem.Source: §A.4 · p. 58
Loading 2610.36577v1…