{"id":"2a9157e2-1f79-4b03-874a-07729a937a63","arxiv_id":"2607.14644","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A new blueprint framework proves single-pass semi-streaming matching cannot beat (8−2√10)/3 ≈ 0.558 approximation.","lead":"This paper introduces a 'blueprint' framework that turns lower-bound proofs for semi-streaming maximum matching into a finite combinatorial optimization problem. Using it, the authors improve the best known streaming lower bound from 0.590 to 0.558 approximation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim B.4 in the ERS construction is unproved as written: the 'last coordinate' argument fails when d∉S_i, leaving a repairable but real gap in Theorem 1.","rationale":"The reader's weakest assumption was Theorem 1 (the ERS construction), and my stress-test agrees that this is the most load-bearing external ingredient. I refine it to a specific, concrete flaw: Claim B.4's proof that each color class is large uses a false assertion about the last coordinate. Since the rest of the framework relies on r=n/C−δn in Lemma 5.2 and Theorem 2, this gap must be fixed before the lower bound is fully established. However, I do not think it is fatal: a short alternative argument (uniformity of coordinates modulo Q) likely repairs the claim, and the remainder of the proof—blueprint expansion, weak inducedness, the compression lemma, and the algebra in Lemma 6.6—appears internally consistent after review. The Section 7 'Follow up work' overclaim is a presentation issue rather than a correctness issue for Theorem 4. Because the reader's CONDITIONAL verdict already reflects the need for independent checking of the ERS construction, my finding does not change the verdict. I would, however, ask the authors to correct Claim B.4 before final publication, and ideally to spell out the uniform-mod-Q argument.","tokens_in":44050,"tokens_out":25208,"duration_ms":244791,"concrete_test":"Analytically or by a small script, fix C=2, δ=1/80, d=80 (so p=6400, Q=200, Q|p) and pick S_i not containing d, e.g. S_i={1}. Count the fraction of v∈[p]^d with weight_i(v) mod Q in [0,80) (color 1). If the fraction is exactly 80/200=0.4, Claim B.4's conclusion holds despite the erroneous 'last coordinate' justification; if it differs, Theorem 1 is false and the lower bound collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central lower bound depends on Theorem 1 (Appendix B), which provides the (C,r,t)-ERS graphs with r=n/C−δn and t=n^{Ω(1/log log n)}. A concrete gap appears in Claim B.4, which asserts that because Q|p, 'the last coordinate of a vector determines its weight_i(·) mod Q', so each color class L_i,x has density at least (1−10Cδ)/C. But weight_i(v)=Σ_{k∈S_i} v_k, so if the last coordinate d is not in S_i, changing v_d does not change weight_i at all. Claim B.1 does not guarantee d∈S_i, nor that the last coordinate is in every S_i. Thus the stated justification does not prove the size lower bound. If the actual color-class density were smaller for some x, then r=n/C−δn in Theorem 1 would fail, and with it Lemma 5.2's canonical matching size and the final n^{1+Ω(1/log log n)} space bound. The gap is probably repairable: since p is a multiple of Q, every coordinate is uniform mod Q, and because S_i is nonempty, weight_i mod Q is exactly uniform, giving color-class density B/Q. But that argument is not what the paper writes, and the proof as printed is incomplete at a load-bearing point.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":44428,"tokens_out":15301,"duration_ms":153741,"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":[{"comment":"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","section":"Appendix B, Claim B.4"}],"minor_comments":[{"comment":"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.","section":"Appendix B, first paragraph"},{"comment":"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.","section":"§5.2, Lemma 5.4 proof"},{"comment":"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.","section":"§5.2, Lemma 5.2 part 2"}],"recommendation":"major_revision","confidential_remarks":"The gap in Claim B.4 is real but localized, and the sketched fix is short; if the authors supply a corrected proof, I would support acceptance. I would also ask the editor to confirm how the 'Follow up work' note and the STOC 2026 notice are handled in the journal version, since the note asserts a stronger follow-up result by the same authors."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. First, the blueprint framework is a real step forward: it turns semi-streaming matching lower bounds into a finite combinatorial optimization problem, recovers 2/3 and 2−√2 cleanly, and gives a new 0.558 bound. Second, the proof as written has a load-bearing gap in the ERS graph construction (Claim B.4). It's probably repairable, but it needs fixing before the main theorem is solid.\n\nThe framework itself is the actual contribution. Blueprints abstract away the RS graph machinery and the information-theoretic arguments, and the expansion argument in Section 4 is genuinely elegant. The communication lower bound in Section 5 is modular and the counting seems internally consistent. The paper is also honest about what it does and doesn't prove; the 'best possible' phrasing in Section 6 is too strong, but the technical claims are stated accurately.\n\nThe soft spots are localized. Claim B.4 asserts that the last coordinate determines weight_i mod Q because Q divides p. That only works if the last coordinate is in S_i, and Claim B.1 doesn't guarantee it. Without that, the color-class density lower bound isn't proven, and Theorem 1—which the whole lower bound leans on—is incomplete. The fix is straightforward: use any coordinate in S_i; since p is a multiple of Q, that coordinate alone makes the sum uniform mod Q. So I'd call this a repairable gap, not a fatal flaw, but it has to be fixed. The other worry is that the lower bound depends on an existential ERS graph with very specific parameters; the proof is not machine-checked and the recursive blueprint construction is complex. I haven't spotted a circularity, and the new numerical bound is not an input to the construction.\n\nThis paper is for streaming and communication complexity people. It deserves a serious referee—the framework is important enough that the community should see it, and the gap is likely fixable. I'd send it to review but explicitly ask for a clean proof of Claim B.4 and a correction of the overclaim in Section 6.","headline":"Blueprint framework is a genuine advance; the 0.558 bound is real if a repairable gap in Claim B.4 is fixed.","tokens_in":44864,"tokens_out":3604,"would_cite":true,"duration_ms":34930,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C70","68Q17","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["semi-streaming algorithms","maximum matching","lower bounds","blueprints","Ruzsa-Szemerédi graphs","communication complexity","single-pass algorithms","approximation ratio"],"falsifier":"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.","tokens_in":43970,"feed_emoji":"🧩","tokens_out":8530,"duration_ms":89679,"temperature":0.7,"pith_summary":"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.","feed_headline":"Matching lower bound: one pass cannot beat 0.558","feed_subtitle":"New blueprint framework turns streaming lower bounds into a search over tiny graphs, improving 0.590 to 0.558.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Blueprint framework pushes matching lower bound to 0.558","Tiny graphs prove single-pass matching can't beat 0.558","New blueprint method tightens semi-streaming bound to 0.558","Lower bound improved: single-pass matching capped at 0.558","Blueprints simplify and strengthen streaming matching bounds"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Blueprint framework pushes matching lower bound to 0.558","Tiny graphs prove single-pass matching can't beat 0.558","New blueprint method tightens semi-streaming bound to 0.558","Lower bound improved: single-pass matching capped at 0.558","Blueprints simplify and strengthen streaming matching bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000153,"raw_usage":{"total_tokens":1093,"prompt_tokens":843,"completion_tokens":250,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":587,"completion_tokens_details":{"reasoning_tokens":164}},"tokens_in":587,"tokens_out":250,"duration_ms":3022,"temperature":1.0,"reasoning_tokens":164,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T01:28:34.319351+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}