Pith. sign in

REVIEW 4 major objections 6 minor 52 references

Space Complexity of Minimum Cut Problems in Single-Pass Streams

T0 review · 4 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict Strong and probably right, but the main space bound rests on a short-cycle-decomposition claim that is asserted, not proven. read the letter →

arxiv 2412.01143 v2 pith:G4CR7BG2 submitted 2024-12-02 cs.DS

Matthew Ding , Alexandro Garces , Jason Li , Honghao Lin , Jelani Nelson , Vihan Shah , David P. Woodruff This is my paper · ORCID
classification cs.DS MSC 68W2005C8568Q17
keywords minimumcutgraphstreamingspectralsparsificationfor-eachsparsifiershort-cycledecompositionrandom-orderstreamseffectiveresistancespacelowerbounds
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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).
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 6 minor

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.

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 (4)
  1. [Section 4.3, proof of Lemma 3.2] 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.
  2. [Sections 1.1 and 4.4; Definition 1.3] 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.
  3. [Section 4.6, Theorem 3.5 and Lemma 4.12] 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.
  4. [Section 4.1, Lemma 4.2] 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.
minor comments (6)
  1. [Section 2.2, Claim 2.2] 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.
  2. [Section 4.2, Lemma 4.4] 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.
  3. [Section 5.1, Algorithm 2] 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.
  4. [Section 5.1, Lemma 5.1] 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.
  5. [Section 5.1] 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.
  6. [Section 5.1] The notation '1.12s' should be written as '1.1^2 · s' to avoid ambiguity about whether it is a decimal or an exponent.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: main upper bounds use external sparsifier and short-cycle results; lower bounds use independent published lower bounds, and the only flagged concern is an unproved coverage assertion in Lemma 4.2, which is a correctness gap rather than a circular reduction.

full rationale

The paper's positive result (Theorem 3.1) is built on Lemma 3.2, whose proof combines the CGP+18 graphical for-each spectral sketch framework, the PY19 short-cycle decomposition, and the BDM+20 merge-and-reduce lemma; these are cited prior theorems rather than restatements of the paper's own definitions. The in-paper modification in Lemma 4.2 truncates the PY19 cycle cover at O(m) edges and asserts that the greedy edge-disjoint selection still covers an Omega(1/(dc)) fraction of all uncovered edges, so the iteration count is preserved. That assertion is not proved in the text; however, it is a coverage claim about a prefix of the cycle cover, not an equation forced by the construction, so it is an omitted-proof/correctness risk, not circularity. The lower bounds in Theorem 3.4 and 3.5 reduce to the k-edge-connectivity lower bound of Sun and Woodruff [SW15], the cut-sparsifier lower bound of Andoni et al. [ACK+16], and the Index lower bound [KN96]; two of these are co-authored by a present author, but they are separately published theorems with their own proofs, invoked as external facts. No fitted parameter is renamed as a prediction, and no target quantity is defined in terms of the algorithm's own output. The central O~(n/epsilon) space claim therefore has independent content; the paper's circularity score is 0.

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

The central claims rest on a chain of prior streaming, sparsification, and communication complexity results, all of which are cited. No free parameters are fitted to data, and no new entities are postulated.

assumptions (8)
  • domain assumption Lemma 4.1 ([CGP+18]): a for-each spectral sparsifier with n^{1+o(1)}/ε edges can be computed in m^{1+o(1)} time.
    Relied on for the SpectralSketch subroutine in Algorithm 1 and Lemma 3.2.
  • domain assumption Lemma 2 of [PY19]: a low-congestion cycle cover with cycles of length O(log^2 n) covering all but O(n log n) edges can be computed in almost-linear time.
    Used in Lemma 4.2 to derive the near-linear space short-cycle decomposition.
  • domain assumption Lemma 1.4 ([KMM+20]): a one-pass streaming algorithm outputs a (1+ε)-spectral sparsifier using O-tilde(n/ε^2) space.
    Used in the min-cut algorithm to find candidate cuts and in the random-order exact min-cut algorithm.
  • standard math Lemma 4.6 ([Kar00]): the number of α-approximate minimum cuts is O(n^{⌊2α⌋}).
    Basis for the union bound over candidate cuts in Theorem 3.1.
  • standard math Lemma 5.2 ([RSW18]): the total number of edges participating in non-singleton (2-ε)-approximate minimum cuts is O(n).
    Critical for the space bound in the random-order exact min-cut algorithm.
  • standard math Claim 4.8 ([SW15]): k-edge-connectivity in insertion-only streams requires Ω(kn) bits for randomized algorithms and Ω(kn log n) for deterministic.
    Used for the randomized lower bound in Theorem 3.4.
  • standard math Lower bound of [ACK+16] for for-all cut sparsifiers: Ω(n log n/ε^2) bits.
    Used in Lemma 4.10 to derive the deterministic Ω(n/ε^2) lower bound.
  • domain assumption Lemma 4.12 ([OS23]): concentration of hitting times in G(n,p).
    Used in Theorem 3.5; the paper transfers it to bipartite Erdos-Renyi graphs without proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Space Complexity of Minimum Cut Problems in Single-Pass Streams." pith.science (2026). https://pith.science/paper/G4CR7BG2

@misc{pith2026241201143,
  author       = {Pith},
  title        = {Pith review of: Space Complexity of Minimum Cut Problems in Single-Pass Streams},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G4CR7BG2}},
  note         = {Machine review of arXiv:2412.01143}
}
abstract

We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. While graph sparsification in streams has been intensively studied, the specific application of finding minimum cuts in streams is less well-studied. To this end, we show upper and lower bounds on minimum cut problems in insertion-only streams for a variety of settings, including for both randomized and deterministic algorithms, for both arbitrary and random order streams, and for both approximate and exact algorithms. One of our main results is an $\widetilde{O}(n/\varepsilon)$ space algorithm with fast update time for approximating a spectral cut query with high probability on a stream given in an arbitrary order. Our result breaks the $\Omega(n/\varepsilon^2)$ space lower bound required of a sparsifier that approximates all cuts simultaneously. Using this result, we provide streaming algorithms with near optimal space of $\widetilde{O}(n/\varepsilon)$ for minimum cut and approximate all-pairs effective resistances, with matching space lower-bounds. The amortized update time of our algorithms is $\widetilde{O}(1)$, provided that the number of edges in the input graph is at least $(n/\varepsilon^2)^{1+o(1)}$. We also give a generic way of incorporating sketching into a recursive contraction algorithm to improve the post-processing time of our algorithms. In addition to these results, we give a random-order streaming algorithm that computes the {\it exact} minimum cut on a simple, unweighted graph using $\widetilde{O}(n)$ space. Finally, we give an $\Omega(n/\varepsilon^2)$ space lower bound for deterministic minimum cut algorithms which matches the best-known upper bound up to polylogarithmic factors.

Figures

Figures reproduced from arXiv: 2412.01143 by the authors.

Figure 1
Figure 1. Construction of graph H+ for exact minimum cut from [Zel11]. Red nodes are the ones that are added in addition to the original graph. A.2 Approximate Minimum Cut We are ready to give proof for Theorem 3.4. First, we assume that 1/ε < n, as otherwise there already exists the known Ω(n 2 ) lower bound for minimum cut. Additionally, we assume ε = o(1), as a constant approximation for minimum cut answers whether a graph… view at source ↗
Figure 2
Figure 2. Construction of graph H+(ε) for approximate minimum cut. Red nodes are the ones that are added in addition to the original graph. Gi represents the graph containing (potential) edge ab, and G0 and G1 represent the remaining graphs. The double arrow edges represent bicliques between graph G0 ∈ GS and S, and graph G1 ∈ GT and T. C2, as shown by the following claim: Claim A.1. All graph cuts in H+(ε) besides C1 and C2 … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 46 canonical work pages

  1. [1]

    Beating Two-Thirds For Random-Order Streaming Matching

    Sepehr Assadi and Soheil Behnezhad. Beating Two-Thirds For Random-Order Streaming Matching . In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) , volume 198 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 19:1--19:13, Dagstuhl, Germany, 202...

    work page 2021

  2. [2]

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

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

    2019

  3. [3]

    Woodruff, and Qin Zhang

    Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, and Qin Zhang. On sketching quadratic forms. In Madhu Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS) , pages 311--319, 2016

    work page 2016

  4. [4]

    A Simple Semi-Streaming Algorithm for Global Minimum Cuts , pages 172--180

    Sepehr Assadi and Aditi Dudeja. A Simple Semi-Streaming Algorithm for Global Minimum Cuts , pages 172--180. Society for Industrial and Applied Mathematics, 01 2021

    work page 2021

  5. [5]

    On the edge-expansion of graphs

    Noga Alon. On the edge-expansion of graphs. Combinatorics, Probability and Computing , 6(2):145--152, 1997

    work page 1997

  6. [6]

    Woodruff, and Samson Zhou

    Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020 , pages 517--528. IEEE , 2020

    work page 2020

  7. [7]

    Improved bounds for matching in random-order streams

    Aaron Bernstein. Improved bounds for matching in random-order streams. Theory of Computing Systems , pages 1--15, 2023

    work page 2023

  8. [8]

    Bencz \' u r and David R

    Andr \' a s A. Bencz \' u r and David R. Karger. Approximating s-t minimum cuts in \ O (n\( ^ 2 \)) time. In Gary L. Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996 , pages 47--55. ACM , 1996

    work page 1996

Show all 52 references
  1. [9]

    Bencz \' u r and David R

    Andr \' a s A. Bencz \' u r and David R. Karger. Randomized approximation schemes for cuts and flows in capacitated graphs. SIAM J. Comput. , 44(2):290--319, 2015

    2015

  2. [10]

    Batson, Daniel A

    Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice- R amanujan sparsifiers. SIAM J. Comput. , 41(6):1704--1721, 2012

    2012

  3. [11]

    Robust lower bounds for communication and stream computation

    Amit Chakrabarti, Graham Cormode, and Andrew McGregor. Robust lower bounds for communication and stream computation. Theory of Computing , 12(10):1--35, 2016

    2016

  4. [12]

    Testable properties in general graphs and random order streaming

    Artur Czumaj, Hendrik Fichtenberger, Pan Peng, and Christian Sohler. Testable properties in general graphs and random order streaming. arXiv preprint arXiv:1905.01644 , 2019

    1905 arXiv

  5. [13]

    Vertex ordering problems in directed graph streams

    Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, and Sofya Vorotnikova. Vertex ordering problems in directed graph streams. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1786--1802. SIAM, 2020

    2020

  6. [14]

    Graph sparsification, spectral sketches, and faster resistance computation, via short cycle decompositions

    Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, and Junxing Wang. Graph sparsification, spectral sketches, and faster resistance computation, via short cycle decompositions. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer S...

    2018

  7. [15]

    Optimal lower bounds for sketching graph cuts

    Charles Carlson, Alexandra Kolla, Nikhil Srivastava, and Luca Trevisan. Optimal lower bounds for sketching graph cuts. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2565--2569. SIAM, 2019

    2019

  8. [16]

    Cohen, Cameron Musco, and Jakub Pachocki

    Michael B. Cohen, Cameron Musco, and Jakub Pachocki. Online row sampling. Theory of Computing , 16(15):1--25, 2020

    2020

  9. [17]

    Approximate maximum matching in random streams

    Alireza Farhadi, Mohammad Taghi Hajiaghayi, Tung Mah, Anup Rao, and Ryan A Rossi. Approximate maximum matching in random streams. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1773--1785. SIAM, 2020

    2020

  10. [18]

    Graph distances in the data-stream model

    Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the data-stream model. SIAM J. Comput. , 38:1709--1727, 12 2008

    2008

  11. [19]

    Weighted matchings via unweighted augmentations

    Buddhima Gamlath, Sagar Kale, Slobodan Mitrovic, and Ola Svensson. Weighted matchings via unweighted augmentations. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing , pages 491--500, 2019

    2019

  12. [20]

    Gilbert, Yi Li, Ely Porat, and Martin J

    Anna C. Gilbert, Yi Li, Ely Porat, and Martin J. Strauss. Approximate sparse recovery: Optimizing time and measurements. SIAM J. Comput. , 41(2):436--453, 2012

    2012

  13. [21]

    Stream order and order statistics: Quantile estimation in random-order streams

    Sudipto Guha and Andrew McGregor. Stream order and order statistics: Quantile estimation in random-order streams. SIAM Journal on Computing , 38(5):2044--2059, 2009

    2009

  14. [22]

    Hendrickx, Karl Henrik Johansson, Raphaël M

    Julien M. Hendrickx, Karl Henrik Johansson, Raphaël M. Jungers, Henrik Sandberg, and Kin Cheong Sou. Efficient computations of a security index for false data attacks in power networks. IEEE Transactions on Automatic Control , 59(12):3194--3208, 2014

    2014

  15. [23]

    Weighted matching in the random-order streaming and robust communication models

    Diba Hashemi and Weronika Wrzos-Kaminska. Weighted matching in the random-order streaming and robust communication models. arXiv preprint arXiv:2408.15434 , 2024

    2024 arXiv

  16. [24]

    Efficient \ o (n/eps) spectral sketches for the laplacian and its pseudoinverse

    Arun Jambulapati and Aaron Sidford. Efficient \ o (n/eps) spectral sketches for the laplacian and its pseudoinverse. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2487--2503. SIAM, 2018

    2018

  17. [25]

    Space lower bounds for approximating maximum matching in the edge arrival model

    Michael Kapralov. Space lower bounds for approximating maximum matching in the edge arrival model. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '21, page 1874–1893, USA, 2021. Society for Industrial and Applied Mathematics

    2021

  18. [26]

    David R. Karger. Minimum cuts in near-linear time. J. ACM , 47(1):46--76, 2000

    2000

  19. [27]

    Approximating matching size from random streams

    Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Approximating matching size from random streams. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms , pages 734--751. SIAM, 2014

    2014

  20. [28]

    Karger and Matthew S

    David R. Karger and Matthew S. Levine. Random sampling in residual graphs. In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montr \' e al, Qu \' e bec, Canada , pages 63--66. ACM , 2002

    2002

  21. [29]

    Single pass spectral sparsification in dynamic streams

    Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single pass spectral sparsification in dynamic streams. SIAM J. Comput. , 46(1):456--477, 2017

    2017

  22. [30]

    Maximum matching in semi-streaming with few passes

    Christian Konrad, Fr \'e d \'e ric Magniez, and Claire Mathieu. Maximum matching in semi-streaming with few passes. In International Workshop on Approximation Algorithms for Combinatorial Optimization , pages 231--242. Springer, 2012

    2012

  23. [31]

    Fast and space efficient spectral sparsification in dynamic streams

    Michael Kapralov, Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, and Jakab Tardos. Fast and space efficient spectral sparsification in dynamic streams. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '2...

    2020

  24. [32]

    Communication Complexity

    Eyal Kushilevitz and Noam Nisan. Communication Complexity . Cambridge University Press, 1996

    1996

  25. [33]

    A simple augmentation method for matchings with applications to streaming algorithms

    Christian Konrad. A simple augmentation method for matchings with applications to streaming algorithms. In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 , pages 74--1. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publ...

    2018

  26. [34]

    Karger and Clifford Stein

    David R. Karger and Clifford Stein. A new approach to the minimum cut problem. J. ACM , 43(4):601--640, 1996

    1996

  27. [35]

    Fast approximation algorithms for cut-based problems in undirected graphs

    Aleksander Madry. Fast approximation algorithms for cut-based problems in undirected graphs. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA , pages 245--254. IEEE Computer Society, 2010

    2010

  28. [36]

    Graph stream algorithms: A survey

    Andrew McGregor. Graph stream algorithms: A survey. SIGMOD Rec. , 43(1):9–20, may 2014

    2014

  29. [37]

    Testable bounded degree graph properties are random order streamable

    Morteza Monemizadeh, Shan Muthukrishnan, Pan Peng, and Christian Sohler. Testable bounded degree graph properties are random order streamable. arXiv preprint arXiv:1707.07334 , 2017

    2017 arXiv

  30. [38]

    Weighted min-cut: sequential, cut-query, and streaming algorithms

    Sagnik Mukhopadhyay and Danupon Nanongkai. Weighted min-cut: sequential, cut-query, and streaming algorithms. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020 , pages 496--509. ACM , 2020

    2020

  31. [39]

    Munro and M.S

    J.I. Munro and M.S. Paterson. Selection and sorting with limited storage. Theoretical Computer Science , 12(3):315--323, 1980

    1980

  32. [40]

    Concentration of hitting times in erd o s-r \'e nyi graphs

    Andrea Ottolini and Stefan Steinerberger. Concentration of hitting times in erd o s-r \'e nyi graphs. Journal of Graph Theory , 2023

    2023

  33. [41]

    Estimating graph parameters from random order streams

    Pan Peng and Christian Sohler. Estimating graph parameters from random order streams. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2449--2466. SIAM, 2018

    2018

  34. [42]

    Optimal short cycle decomposition in almost linear time

    Merav Parter and Eylon Yogev. Optimal short cycle decomposition in almost linear time. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 , Leibniz International Proceedings in Informatics, LIPIcs. Schloss Dagstuhl- Leibniz-Zentrum fur Informa...

    2019

  35. [43]

    Matthew Weinberg

    Aviad Rubinstein, Tselil Schramm, and S. Matthew Weinberg. Computing exact minimum cuts without knowing the graph. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA , volume 94 of LIPIcs , ...

    2018

  36. [44]

    Breaking the multicommodity flow barrier for o(vlog n)-approximations to sparsest cut

    Jonah Sherman. Breaking the multicommodity flow barrier for o(vlog n)-approximations to sparsest cut. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA , pages 363--372. IEEE Computer Society, 2009

    2009

  37. [45]

    Isolation vulnerability analysis in road network: Edge connectivity and critical link sets

    Satoshi Sugiura and Fumitaka Kurauchi. Isolation vulnerability analysis in road network: Edge connectivity and critical link sets. Transportation Research Part D: Transport and Environment , 119:103768, 2023

    2023

  38. [46]

    Spielman and Nikhil Srivastava

    Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J. Comput. , 40(6):1913--1926, 2011

    1913

  39. [47]

    Spielman and Shang - Hua Teng

    Daniel A. Spielman and Shang - Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In L \' a szl \' o Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16,...

    2004

  40. [48]

    Spielman and Shang - Hua Teng

    Daniel A. Spielman and Shang - Hua Teng. Spectral sparsification of graphs. SIAM J. Comput. , 40(4):981--1025, 2011

    2011

  41. [49]

    Woodruff

    Xiaoming Sun and David P. Woodruff. Tight Bounds for Graph Problems in Insertion Streams . In Naveen Garg, Klaus Jansen, Anup Rao, and Jos \'e D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) , v...

    2015

  42. [50]

    Efficient targeted influence minimization in big social networks

    Xinjue Wang, Ke Deng, Jianxin Li, Jeffery Xu Yu, Christian S Jensen, and Xiaochun Yang. Efficient targeted influence minimization in big social networks. World Wide Web , 23(4):2323--2340, 2020

    2020

  43. [51]

    Williamson

    David P. Williamson. Lecture notes in spectral graph theory, October 2016. https://people.orie.cornell.edu/dpw/orie6334/Fall2016/lecture13.pdf

    2016

  44. [52]

    Intractability of min- and max-cut in streaming graphs

    Mariano Zelke. Intractability of min- and max-cut in streaming graphs. Information Processing Letters , 111(3):145--150, 2011

    2011

Pith tools

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