{"id":"dc5f2f35-3f49-472c-ae88-32958c8e5480","arxiv_id":"2412.01143","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper constructs a for-each spectral sparsifier in O-tilde(n/ε) streaming space, breaking the Ω(n/ε^2) for-all sparsifier barrier, and uses it for near-optimal minimum cut and effective resistance algorithms.","lead":"This paper shows that a graph's minimum cut can be approximated in a single-pass stream using only O-tilde(n/ε) bits of memory, matching the information-theoretic lower bound and beating the O-tilde(n/ε^2) required by general sparsifiers. It also gives the first exact minimum cut algorithm for random-order streams and proves matching lower bounds across several streaming models.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The main Õ(n/ε) space upper bound depends on Lemma 4.2's early-terminated short-cycle decomposition, whose prefix coverage/congestion guarantee is asserted but not proven; if that trade-off fails, the for-each sparsifier edge bound degrades and Theorem 3.1 collapses.","rationale":"The reader's weakest-assumption choice, Lemma 4.2, is also the most load-bearing gap for the paper's central claim. Theorem 3.1's space advantage over the Ω(n/ε^2) for-all lower bound is exactly the eO(n/ε) edge count of the for-each sparsifier, and that count is only as strong as Lemma 4.2's space-efficient short-cycle decomposition. The proof sketch gives a plausible argument, but the key inference from a completed-cycle-cover guarantee to a prefix guarantee is not justified in the text. I do not see an obvious counterexample, which is why the appropriate verdict is conditional verification rather than rejection. A secondary concern is the JL-sketch post-processing in §4.4: the analysis states O(N log n/ε^2) words per recursion level, which at N=n exceeds eO(n/ε) bits; this is likely fixable by using a sparse JL/CountSketch and storing only the O(m_H) nonzeros of the column sketch, but as written the post-processing space analysis is overclaimed. That issue is less load-bearing because it affects the claimed post-processing time rather than the existence of an eO(n/ε)-space streaming algorithm with slower post-processing. Overall, the reader's CONDITIONAL verdict is appropriate and should stand.","tokens_in":24585,"tokens_out":36519,"duration_ms":336459,"concrete_test":"Re-derive Lemma 4.2 from the full version of [PY19] (Lemma 2 and the ImprovedShortCycleDecomp procedure). Specifically, on a worst-case graph, run the low-congestion cycle-cover construction and stop after O(m) edge-occurrences; verify whether (a) the partial cycle cover has congestion at most c, and (b) the greedy edge-disjoint selection covers Ω(1/(dc)) of the currently uncovered edges. If an input family exists where this prefix covers o(m) distinct uncovered edges, Lemma 4.2 fails and the edge bound of Lemma 3.2 degrades to n^{1+o(1)}/ε, invalidating the Õ(n/ε) space claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central positive result (Theorem 3.1) rests on Lemma 3.2's streaming for-each spectral sparsifier, and Lemma 3.2 inherits its eO(n/ε) edge bound from Lemma 4.3, which relies on Lemma 4.2. Lemma 4.2 claims an eO(m)-space version of the [PY19] short-cycle decomposition by terminating the low-congestion cycle cover once it contains O(m) edge-occurrences. The proof correctly notes that early termination cannot increase congestion, but it then asserts that the greedy edge-disjoint cycle selection still covers an Ω(1/(dc)) fraction of all uncovered edges. This does not follow from the [PY19] guarantee alone: that guarantee applies to the completed cycle cover (all but O(n log n) edges covered with congestion c), whereas a prefix of the construction has no stated coverage guarantee. If the first O(m) edge-occurrences are concentrated on a small set of distinct edges, the greedy selection removes too few currently uncovered edges, the number of iterations grows, and the final graph may have n^{1+o(1)}/ε edges rather than eO(n/ε). Since Lemma 4.3 and hence Lemma 3.2 are built on this step, the main space bound of Theorem 3.1 is not fully established without a precise verification of the prefix coverage behavior.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the space complexity of minimum cut problems in single-pass insertion-only streams. The main result is a one-pass randomized algorithm that computes a (1+ε)-approximate minimum cut on weighted graphs using O~(n/ε) bits of space (Theorem 3.1), obtained from a new streaming construction of a graphical for-each spectral sparsifier with O~(n/ε) edges and O~(n/ε) bits of space (Lemma 3.2). The technical core is a space-efficient version of the short-cycle decomposition of Parter and Yogev (Lemma 4.2), combined with online leverage score sampling and a merge-and-reduce framework. The paper also gives an O~(n)-space exact minimum cut algorithm for simple unweighted graphs in random-order streams (Theorem 3.6), an Ω(n/ε) lower bound for randomized approximate minimum cut and all-pairs effective resistance, and an Ω(n/ε^2) lower bound for deterministic approximate minimum cut. The lower bounds are mostly reductions from known results on k-edge-connectivity and cut sparsification, with one self-contained Index-based proof in the appendix.","tokens_in":24834,"tokens_out":38507,"duration_ms":350528,"significance":"If the proofs are completed, the main result is significant: it shows that approximating the minimum cut in a single-pass stream can be done in O~(n/ε) space, breaking the Ω(n/ε^2) space barrier that a for-all cut or spectral sparsifier must pay, and it matches the Ω(n/ε) for-each sketching lower bound up to polylogarithmic factors. The random-order exact minimum cut result is also notable, achieving O~(n) space and matching the connectivity lower bound. The paper gives explicit algorithms with near-linear amortized update time under a mild density condition, and it identifies a useful application to all-pairs effective resistances. The lower-bound arguments are mostly clean reductions from prior work; the self-contained appendix provides a useful alternative proof. The main concern is that several load-bearing proof details are under-specified or cite the wrong lemma, and one lower bound applies an Erdős-Rényi hitting-time result to random bipartite graphs without justification.","major_comments":[{"comment":"The space analysis of Lemma 3.2 states that 'From Lemma 4.1 we have that each call to the subroutine SpectralSketch takes at most eO(mspace · log(n/ε)) words of space'. Lemma 4.1, however, only gives a for-each spectral sparsifier with n^{1+o(1)}/ε edges; using that guarantee inside the merge-and-reduce framework would yield block size n^{1+o(1)} log(n/ε)/ε and would not give the claimed eO(n/ε) space bound. The proof must instead use Lemma 4.3, whose eO(n/ε) edge bound derives from the improved short-cycle decomposition (Lemma 4.2), and the space derivation should be reworked accordingly.","section":"Section 4.3, proof of Lemma 3.2"},{"comment":"Definition 1.3 fixes a per-query success probability of 2/3, but the proofs of Theorem 3.1 and Lemma 3.2 union bound over poly(n) candidate cuts and over O(log(n/ε)) calls. With only the constant per-query guarantee, simultaneous success for all candidate cuts is not high probability, and the statement in the proof of Lemma 3.2 that 'each call to this subroutine is successful with high probability after taking a union bound' is not a consequence of Definition 1.3. Please either strengthen the for-each guarantee to failure probability 1/poly(n) per query and verify that the construction supports this amplification within eO(n/ε) space, or state explicitly that O(log n) independent copies of the sparsifier are kept and the median is taken for each cut.","section":"Sections 1.1 and 4.4; Definition 1.3"},{"comment":"The lower bound construction partitions the graph into disjoint bipartite graphs Gi and then invokes Lemma 4.12, which is a concentration result for hitting times in Erdős-Rényi G(n,p), on each Gi. The manuscript does not justify applying this result to random bipartite graphs; random walks on bipartite graphs have parity constraints that are absent in G(n,p), so the stated formula need not transfer. Since the (1+ε)-separation of effective resistances rests on this lemma, the proof is incomplete as written. The authors should either cite or prove a bipartite analogue of Lemma 4.12, or modify the encoding so that each Gi is an Erdős-Rényi graph.","section":"Section 4.6, Theorem 3.5 and Lemma 4.12"},{"comment":"The proof of Lemma 4.2 asserts that terminating the low-congestion cycle cover of [PY19] once it has O(m) edge-occurrences does not affect the claim that the greedy edge-disjoint selection covers Ω(1/(dc)) of all uncovered edges. This does not follow from the completed-cover guarantee alone, and the manuscript does not provide the charging argument. The claim is salvageable: for a prefix with T=Θ(m) edge-occurrences and congestion c, a maximal edge-disjoint sub-collection covers at least T/(cd) distinct edges, since each selected edge can intersect at most cd occurrences in the prefix. Please add this argument, because the iteration count of the short-cycle decomposition, and hence the eO(n/ε) edge bound of Lemma 4.3, depends on it.","section":"Section 4.1, Lemma 4.2"}],"minor_comments":[{"comment":"Claim 2.2 says 'returns a (1+ε)-spectral sparsifier', but in context it must mean a for-each spectral sparsifier; a for-all spectral sparsifier with eO(n/ε) edges would contradict known lower bounds. Please make the quantifier explicit.","section":"Section 2.2, Claim 2.2"},{"comment":"The statement that online leverage score sampling uses 'O(n log^2 n) bits of working memory' is surprising, since the sampled rows themselves have to be output or stored somewhere. Please clarify whether the sampled edges are streamed directly to the next stage and whether the stated memory bound excludes the output edges.","section":"Section 4.2, Lemma 4.4"},{"comment":"The control flow around line 13 is confusing: if the first loop finishes without hitting the break condition, then all edges of the stream have been processed, and the condition 'if there is no new edge in the stream' is not a meaningful check. Please rewrite the pseudocode to make the two cases (minimum cut below or above the c log n threshold) explicit.","section":"Section 5.1, Algorithm 2"},{"comment":"The indicator variables ye for edges in a random-order prefix are not independent, since the prefix is a uniformly random subset of a fixed size; please state that the Chernoff bound applies because the variables are negatively associated, or use a hypergeometric tail bound.","section":"Section 5.1, Lemma 5.1"},{"comment":"The text says 'we will try all powers of 2 for it', but Algorithm 2 does not explicitly implement this and instead appears to check the threshold at powers-of-two edge counts. Please align the narrative with the pseudocode.","section":"Section 5.1"},{"comment":"The notation '1.12s' should be written as '1.1^2 · s' to avoid ambiguity about whether it is a decimal or an exponent.","section":"Section 5.1"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the journal's scope and the main upper bound is a strong result if the proof gaps are repaired. The two issues I would watch most closely in revision are the for-each amplification (Definition 1.3 versus the high-probability union bounds) and the use of the Erdős-Rényi hitting-time lemma on bipartite graphs in Theorem 3.5. Both appear fixable, but they are substantive enough that I would not accept the current version. The self-citations to [SW15] and [ACK+16] are appropriate because those results are used as black boxes; I see no citation concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this paper. It has three genuinely new results: a single-pass for-each spectral sparsifier in Õ(n/ε) space, near-optimal (1+ε)-min-cut with matching lower bound, and an exact min-cut algorithm in random-order streams in Õ(n) space. The random-order result is surprising, and the lower bounds are tight. The high-level approach is sensible: use short-cycle decompositions to build a graphical for-each sparsifier, then apply merge-and-reduce in the stream, and use the sparse-cut structure to recover the min cut.\n\nCredit where due: the authors are careful about update times and post-processing, and they include a self-contained lower-bound proof in the appendix. The citation pattern is fine; the self-citations are to known results that are the right tools.\n\nThe soft spots are real but not necessarily fatal. The main one is Lemma 4.2. The proof of the space-efficient short-cycle decomposition claims that terminating the [PY19] cycle-cover construction after O(m) edge-occurrences still lets the greedy edge-disjoint selection cover an Ω(1/(dc)) fraction of all uncovered edges. That second step does not follow from the cited guarantee. A prefix of the construction could in principle be concentrated on a small set of distinct edges, in which case the greedy step removes fewer uncovered edges per iteration and the final sparsifier could have n^{1+o(1)}/ε edges rather than Õ(n/ε). The authors may be able to fix this with a sharper argument, but as written the main space bound is not fully established. This is the load-bearing part of Theorem 3.1, so a referee needs to verify it carefully.\n\nTwo smaller issues: Theorem 3.5 applies the [OS23] hitting-time concentration for G(n,p) to bipartite random graphs, which is not automatic; the bipartite case needs a separate justification. And the JL-sketch post-processing in Section 4.4 appears to use Õ(n/ε²) words of memory at the root of the recursion, which is fine only if post-processing space is not counted in the streaming space bound; the text is ambiguous on this.\n\nWho is this for? Researchers in streaming graph algorithms and spectral sparsification. The paper deserves a serious referee. The results are important if correct, and the gaps are localized enough that a careful revision could close them. I would accept it for review with the expectation that Lemma 4.2 and the bipartite hitting-time step get tightened.","headline":"Strong and probably right, but the main space bound rests on a short-cycle-decomposition claim that is asserted, not proven.","tokens_in":25446,"tokens_out":10788,"would_cite":true,"duration_ms":92423,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","05C85","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"A single-pass streaming algorithm approximates the global minimum cut of a weighted graph to within (1+ε) using O~(n/ε) bits of space, matching a new lower bound and beating the Ω(n/ε²) cost of for-all sparsification.","keywords":["minimum cut","graph streaming","spectral sparsification","for-each sparsifier","short-cycle decomposition","random-order streams","effective resistance","space lower bounds"],"falsifier":"Run the modified cycle-cover routine on high-girth expander graphs and count the edges left uncovered after the greedy selection; if any instance leaves ω(n log n) edges uncovered or creates an edge of congestion ω($n^{{o(1)}}$), then the output spectral sketch would have $n^{{1+o(1)}}$ edges and the claimed O~(n/ε) space bound would fail.","tokens_in":24350,"feed_emoji":"✂️","tokens_out":7660,"duration_ms":65264,"temperature":0.7,"pith_summary":"This paper establishes that the global minimum cut of a weighted graph can be approximated to a (1+ε) factor in a single pass over an insertion-only stream using O~(n/ε) bits of memory, matching a new lower bound up to logarithmic factors. The key move is to replace the usual requirement of a sparsifier that approximates every cut at once (for-all, which needs Ω(n/ε²) space) with a for-each sparsifier that only answers one cut query at a time. The paper builds such a sparsifier in a stream, applies it to minimum cut and all-pairs effective resistances, and complements the upper bounds with tight lower bounds. It also shows that in random-order streams, exact minimum cut on simple unweighted graphs is possible in O~(n) space, which is optimal up to polylog factors. If correct, these results close the space complexity of single-pass minimum cut in several settings.","feed_headline":"Min-cut queries need only ~O(n/ε) stream bits","feed_subtitle":"A for-each spectral sketch sidesteps the Ω(n/ε²) cost of sparsifying every cut at once.","key_machinery":"The load-bearing object is the graphical for-each spectral sparsifier: a reweighted subgraph H of G such that for each fixed vector x, with high probability x^T L_H x ≈ (1±ε) x^T L_G x, rather than simultaneously for all x. The construction combines three mechanisms: a short-cycle decomposition routine (modified from an existing deterministic decomposition so that it runs in O~(m) space by stopping the cycle cover once it reaches O(m) edges), online leverage-score sampling that thins the stream to O~(n/ε²) edges before invoking the expensive routine, and a merge-and-reduce framework that layers the sparsifier so the per-edge update time stays small. The sparsifier is what carries the argument: it is a graph, so sketches can be merged; it has only O~(n/ε) edges, so the space bound follows; and it is for-each, so the Ω(n/ε²) for-all lower bound does not apply.","core_discovery":"The paper's central claim is that in an insertion-only stream, a (1+ε)-approximation to the minimum cut can be computed with high probability in O~(n/ε) bits—the same order as the information-theoretic lower bound for this task—by maintaining a graphical 'for-each' spectral sparsifier rather than a for-all one. The for-each sparsifier only has to answer one cut query at a time, so it can be built with O~(n/ε) edges and bits; the paper proves this is possible in a single arbitrary-order pass, then turns the sparsifier into a min-cut algorithm by enumerating the polynomially many near-minimum cuts and estimating each with the sparsifier. It also proves matching Ω(n/ε) lower bounds for randomized algorithms and Ω(n/ε²) lower bounds for deterministic ones, and gives a separate O~(n)-space algorithm that finds the exact minimum cut in a random-order stream of a simple unweighted graph.","pith_inferences":["If the for-each/for-all gap is as wide as this paper suggests, other global cut-based quantities that only need a few cuts—like sparsest cut with a bounded number of candidates—may admit streaming algorithms in O~(n/ε) space even when full cut sparsification is expensive.","The early-termination trick that makes the short-cycle decomposition space-efficient may transfer to other graph algorithms that currently pay m^{1+o(1)} memory to store a cycle cover; a direct test is to plug the modified routine into other cycle-based sketching pipelines.","The paper leaves dynamic streams open; its techniques suggest the dynamic-space gap between Ω(n/ε) and O~(n/ε²) might be closed by a lower bound that simulates deletions, but the current proofs only handle insertion-only streams.","For random-order exact min cut, a natural next test is whether the same prefix-learning strategy works for weighted graphs or for recovering all min cuts (the paper recovers them for simple unweighted graphs)."],"forward_implications":["A single-pass randomized stream can report a (1+ε)-approximate minimum cut of a weighted graph in O~(n/ε) bits, matching the paper's Ω(n/ε) lower bound up to polylog factors.","The same O~(n/ε)-space sketch answers approximate all-pairs effective resistance queries, with a matching Ω(n/ε) lower bound for any sketching scheme.","Deterministic single-pass algorithms cannot match the randomized bound: they require Ω(n/ε²) bits, so randomness is essential to the improvement.","Exact minimum cut in a random-order stream of a simple unweighted graph can be found in O~(n) space, optimal up to polylog factors because even connectivity requires Ω(n) space in that model.","The amortized update time is O~(1) when the input has at least (n/ε²)^{1+o(1)} edges, so the space savings do not come at the cost of slow updates on dense inputs."],"supporting_citations":[{"why":"Supplies the short-cycle-decomposition route to for-each spectral sparsifiers (Claim 2.2 and Lemma 4.1) that the streaming algorithm builds on.","marker":"[CGP+18]"},{"why":"Provides the deterministic short-cycle decomposition whose cycle-cover construction Lemma 4.2 truncates to achieve O~(m) space.","marker":"[PY19]"},{"why":"Gives the online leverage-score sampling (Lemma 4.4) that thins the stream to O~(n/ε²) edges before spectral sketching.","marker":"[CMP20]"},{"why":"Establishes the for-each/for-all distinction and the Ω(n/ε) for-each lower bound that the paper's upper bound matches; also supplies the for-all lower bound used for the deterministic Ω(n/ε²) result.","marker":"[ACK+16]"},{"why":"Shows how a for-each spectral sparsifier converts to an all-pairs effective-resistance data structure, used in Corollary 3.3.","marker":"[JS18]"},{"why":"Gives the streaming for-all spectral sparsifier (Lemma 1.4) used to enumerate candidate near-minimum cuts and as a subroutine in the random-order exact algorithm.","marker":"[KMM+20]"},{"why":"Bounds the number of α-approximate minimum cuts by O(n^{⌊2α⌋}), letting the algorithm union-bound over candidates.","marker":"[Kar00]"},{"why":"Supplies the recursive contraction algorithm used to enumerate approximate minimum cuts with faster post-processing.","marker":"[KS96]"},{"why":"Gives the k-edge-connectivity Ω(kn) lower bound that yields the randomized Ω(n/ε) min-cut lower bound.","marker":"[SW15]"},{"why":"Shows only O(n) edges participate in non-singleton near-minimum cuts, which makes the random-order exact algorithm space-efficient.","marker":"[RSW18]"}],"fun_headline_variants":["For-each spectral sketch cuts stream space to O~(n/ε)","Min-cut in single pass: ~O(n/ε) bits, beating sparsifier lower bound","Exact min-cut in O~(n) space for random-order streams","Streaming min-cut: for-each sparsifier sidesteps Ω(n/ε²) cost","Near-optimal space for min-cut queries in insertion-only streams"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire near-linear-space result depends on a single trade-off in the modified short-cycle decomposition: stopping the cycle cover once it reaches O(m) edges must not raise congestion and must still let the greedy selection cover a constant fraction of the uncovered edges; if either fails, the spectral sketch would need $n^{{1+o(1)}}$ edges and the main space bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["For-each spectral sketch cuts stream space to O~(n/ε)","Min-cut in single pass: ~O(n/ε) bits, beating sparsifier lower bound","Exact min-cut in O~(n) space for random-order streams","Streaming min-cut: for-each sparsifier sidesteps Ω(n/ε²) cost","Near-optimal space for min-cut queries in insertion-only streams"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000257,"raw_usage":{"total_tokens":1642,"prompt_tokens":1070,"completion_tokens":572,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":686,"completion_tokens_details":{"reasoning_tokens":465}},"tokens_in":686,"tokens_out":572,"duration_ms":5857,"temperature":1.0,"reasoning_tokens":465,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T04:41:36.259586+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the modified cycle-cover routine on high-girth expander graphs and count the edges left uncovered after the greedy selection; if any instance leaves ω(n log n) edges uncovered or creates an edge of congestion ω($n^{{o(1)}}$), then the output spectral sketch would have $n^{{1+o(1)}}$ edges and the claimed O~(n/ε) space bound would fail.","supporting_citations":[],"review_version":1}