arxiv: 2605.09814 · v1 · submitted 2026-05-10 · 💻 cs.DS · cs.CC

Recognition: no theorem link

Streaming Complexity Separations for Dense and Sparse Graphs

Yang P. Liu , Hoai-An Nguyen , Noah G. Singer , David P. Woodruff

Authors on Pith no claims yet

Pith reviewed 2026-05-12 02:24 UTC · model grok-4.3

classification 💻 cs.DS cs.CC

keywords streaming algorithmsmaximum cutspace complexitydense graphssparse graphsdensest subgraphapproximation algorithmscommunication complexity

0 comments

The pith

Streaming max-cut requires linear space to output an approximate cut in dense graphs but an extra log factor in sparser graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper establishes a sharp separation in the space complexity of streaming algorithms for maximum cut when the algorithm must output the cut. For dense graphs, O(n/ε²) space is sufficient and Ω(n) space is necessary. For graphs with Θ(n/ε²) edges, Ω(n log(ε² n)/ε²) space is required and this is tight when ε is ω(1/√n). A sympathetic reader would care because it shows how the density of the graph stream changes the fundamental space requirements for producing the actual cut, not just its value. Similar separations are shown for densest subgraph and logarithmic improvements for some CSPs and similarity problems in dense streams.

Core claim

We identify a sharp separation in the streaming space complexity of Maximum Cut when the algorithm must output an approximate cut rather than only the approximate value. For dense graphs, O(n/ε²) space is sufficient and Ω(n) space is necessary. In contrast, for graphs with Θ(n/ε²) edges, the problem requires Ω(n log(ε² n)/ε²) space for any ε=ω(1/√n), which is tight. Using similar techniques we prove an analogous sharp separation in the streaming space complexity of Densest Subgraph and show that for every constant-arity CSP over a constant-size alphabet and the Similarity problem the space complexity in dense streams can be improved by shaving a logarithmic factor.

What carries the argument

The distinction between dense graphs and graphs with Θ(n/ε²) edges in the one-pass streaming model, established via communication complexity reductions that force retention of enough information to output the cut in sparse cases while permitting linear-space sampling or compression in dense cases.

If this is right

Dense graphs admit O(n/ε²)-space streaming algorithms that output an approximate max-cut.
Graphs with Θ(n/ε²) edges require Ω(n log(ε² n)/ε²) space to output such a cut, and the bound is tight for ε=ω(1/√n).
The same density separation applies to densest subgraph.
Deterministic streaming algorithms need Ω(n log n/ε²) space even to approximate the value of the maximum cut.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The explicit requirement to output the cut (instead of its value) is what drives the linear lower bound even for dense instances.
The logarithmic gap may vanish if the model is relaxed to multiple passes over the stream.
The same density-dependent technique may produce analogous separations for other output-sensitive graph problems such as clustering or flow.

Load-bearing premise

The lower bounds depend on the algorithm having to output the approximate cut itself rather than only its value, in a single pass over a random-order or adversarial stream.

What would settle it

A one-pass streaming algorithm that outputs a (1-ε) approximate max-cut using o(n) space on a dense graph or o(n log(ε² n)/ε²) space on a graph with Θ(n/ε²) edges when ε=ω(1/√n) would disprove the claimed space lower bounds.

Figures

Figures reproduced from arXiv: 2605.09814 by David P. Woodruff, Hoai-An Nguyen, Noah G. Singer, Yang P. Liu.

**Figure 1.** Figure 1: The value of the cut T in the complete bipartite graph Kb(S). There are edges between S and S; the thick solid edges stay on the same side of T, while the thick dashed edges are cut by T. This cut only has large value if either (i) S is “very close” to T (so that S ∩ T and S ∩ T are large while S ∩ T and S ∩ T are small) or (ii) S is “very close” to T (so that S ∩ T and S ∩ T are small while S ∩ T and S ∩ … view at source ↗

**Figure 2.** Figure 2: The output of the reduction in Algorithms 2 and 3 for n = 2, π : 00 7→ 01, 01 7→ 00, 10 7→ 11, 11 7→ 10, x = 00, and i = 2. Alice contributes the 2 · 2 n = 8 diagonal edges and Bob contributes the 1 + 2n−1 = 3 vertical edges. In this case, there is a four-cycle (highlighted with thick edges), corresponding to the fact that π(x)i = (01)2 = 1. Algorithm 2 Alice’s protocol reducing Permutation-Index to Denses… view at source ↗

read the original abstract

We identify a sharp separation in the streaming space complexity of Maximum Cut when the algorithm must output an approximate cut (rather than only the approximate value). For dense graphs, we show that $O(n/\varepsilon^2)$ space is sufficient and that $\Omega(n)$ space is necessary. In contrast, for graphs with $\Theta(n/\varepsilon^2)$ edges, the situation is markedly different: we show that the problem requires $\Omega(n \log(\varepsilon^2 n)/\varepsilon^2)$ space for any $\varepsilon=\omega(1/\sqrt{n})$, which is tight for the full range of $\varepsilon$. We also give an $\Omega(n \log n/\varepsilon^2)$-space lower bound against deterministic algorithms for outputting a $(1-\varepsilon)$ approximation to the value of the maximum cut. Using similar techniques we prove an analogous sharp separation in the streaming space complexity of Densest Subgraph and show that for every constant-arity CSP over a constant-size alphabet and the Similarity problem the space complexity in dense streams can be improved by shaving a logarithmic factor.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper cleanly separates streaming space for outputting an approximate max-cut on dense graphs versus sparse ones, with matching upper and lower bounds in each regime.

read the letter

The main thing to know is that outputting an approximate max-cut requires O(n/ε²) space on dense graphs but Ω(n log(ε² n)/ε²) space on graphs with Θ(n/ε²) edges, and both sides are tight for ε = ω(1/√n). They get an analogous separation for densest subgraph and note that dense streams let you shave a log factor on some constant-arity CSPs and the similarity problem. A deterministic Ω(n log n / ε²) lower bound for approximating the cut value is included as well.

Referee Report

1 major / 2 minor

Summary. The paper identifies sharp separations in the streaming space complexity of Maximum Cut when the algorithm must output an approximate cut (rather than only its value). For dense graphs, O(n/ε²) space suffices via a vertex-sampling sketch while Ω(n) space is necessary due to output size. For graphs with Θ(n/ε²) edges, an Ω(n log(ε² n)/ε²) lower bound holds for ε=ω(1/√n) via a communication-complexity reduction that forces resolution among many possible sparse cuts, and the bounds are claimed to be tight across the regime. Analogous separations are shown for Densest Subgraph, with logarithmic-factor improvements noted for constant-arity CSPs and Similarity in dense streams. A separate Ω(n log n/ε²) deterministic lower bound is given for approximating the max-cut value.

Significance. If the results hold, the work provides a clear demonstration that requiring the algorithm to output the cut (as opposed to the value) creates qualitatively different space requirements in dense versus sparse regimes. The matching upper and lower bounds, obtained via standard vertex sampling for upper bounds and communication-complexity reductions for lower bounds, constitute a solid technical contribution to streaming graph algorithms. The extensions to Densest Subgraph and other problems broaden the applicability of the separation technique.

major comments (1)

[Abstract] Abstract: The claim that the Ω(n log(ε² n)/ε²) lower bound is tight for the full range of ε requires an explicit matching O(n log(ε² n)/ε²) upper-bound construction for the Θ(n/ε²)-edge case; without seeing the precise statement of this upper bound (likely in the sparse-graph section), it is unclear whether the logarithmic factor is achieved uniformly or only asymptotically outside the ε=ω(1/√n) window.

minor comments (2)

[Abstract] The deterministic Ω(n log n/ε²) lower bound for value approximation is stated in the abstract without indicating whether it applies to the dense or sparse setting; a one-sentence clarification would help readers distinguish it from the main output-cut results.
The notation Θ(n/ε²) for the sparse regime should be accompanied by a brief remark on how the hidden constants interact with the ε=ω(1/√n) condition to ensure the log factor is forced.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive recommendation and careful reading of the manuscript. The observation about the abstract's tightness claim is well-taken, and we address it directly below.

read point-by-point responses

Referee: [Abstract] Abstract: The claim that the Ω(n log(ε² n)/ε²) lower bound is tight for the full range of ε requires an explicit matching O(n log(ε² n)/ε²) upper-bound construction for the Θ(n/ε²)-edge case; without seeing the precise statement of this upper bound (likely in the sparse-graph section), it is unclear whether the logarithmic factor is achieved uniformly or only asymptotically outside the ε=ω(1/√n) window.

Authors: We thank the referee for highlighting this point. Section 4.2 of the manuscript presents an explicit O(n log(ε² n)/ε²)-space streaming algorithm for outputting a (1-ε)-approximate cut on graphs with Θ(n/ε²) edges. The construction combines vertex sampling with a logarithmic-factor sketch to handle the resolution of sparse cut edges, and it holds uniformly for all ε = ω(1/√n). We will revise the abstract to explicitly reference this upper-bound construction and its section, making the tightness claim clearer. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper's upper bounds are obtained via explicit constructions such as vertex-sampling sketches that reconstruct an approximate cut, while lower bounds are derived from reductions to external communication-complexity problems (e.g., indexing or set-disjointness) whose hardness is independent of the present results. The Ω(n) lower bound for dense graphs follows directly from the output-size requirement to specify a partition, and the extra log(ε² n) factor for sparse graphs is forced by the entropy of the cut space in the reduction; neither relies on self-citation chains, fitted parameters renamed as predictions, or ansatzes smuggled from prior author work. The claimed separations are therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Results rest on the standard one-pass streaming model, random-order or adversarial arrival, and communication-complexity reductions; no free parameters or invented entities are introduced.

axioms (2)

domain assumption Standard one-pass streaming model with limited memory and single pass over edge stream
Invoked throughout the abstract for both upper and lower bounds
standard math Communication complexity lower bounds transfer to streaming via standard reductions
Used to obtain the Ω(n log ...) lower bounds

pith-pipeline@v0.9.0 · 5496 in / 1314 out tokens · 22977 ms · 2026-05-12T02:24:46.270895+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

73 extracted references · 73 canonical work pages

[1]

Jaroslaw Blasiok , editor =. Optimal. Proceedings of the Twenty-Ninth Annual. 2018 , url =. doi:10.1137/1.9781611975031.156 , timestamp =

work page doi:10.1137/1.9781611975031.156 2018
[3]

and Yang, Cheng , title =

Cohen, Edith and Datar, Mayur and Fujiwara, Shinji and Gionis, Aristides and Indyk, Piotr and Motwani, Rajeev and Ullman, Jeffrey D. and Yang, Cheng , title =. IEEE Trans. on Knowl. and Data Eng. , month = jan, pages =. 2001 , issue_date =. doi:10.1109/69.908981 , abstract =

work page doi:10.1109/69.908981 2001
[4]

Identifying and Filtering Near-Duplicate Documents

Broder, Andrei Z. Identifying and Filtering Near-Duplicate Documents. Combinatorial Pattern Matching. 2000

work page 2000
[5]

Size-Estimation Framework with Applications to Transitive Closure and Reachability , journal =

Edith Cohen , abstract =. Size-Estimation Framework with Applications to Transitive Closure and Reachability , journal =. 1997 , issn =. doi:https://doi.org/10.1006/jcss.1997.1534 , url =

work page doi:10.1006/jcss.1997.1534 1997
[6]

d - k -min-wise Independent Family of Hash Functions , journal =

Guy Feigenblat and Ely Porat and Ariel Shiftan , keywords =. d - k -min-wise Independent Family of Hash Functions , journal =. 2017 , issn =. doi:https://doi.org/10.1016/j.jcss.2016.09.005 , url =

work page doi:10.1016/j.jcss.2016.09.005 2017
[7]

Estimating Rarity and Similarity over Data Stream Windows

Datar, Mayur and Muthukrishnan, S. Estimating Rarity and Similarity over Data Stream Windows. Algorithms --- ESA 2002. 2002

work page 2002
[8]

2023 , eprint=

Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions , author=. 2023 , eprint=

work page 2023
[9]

Cormode, Graham and Muthukrishnan, Senthilmurugan and Rozenbaum, Irina , year =

work page
[10]

, title =

Karamcheti, Vijay and Geiger, Davi and Kedem, Zvi and Muthukrishnan, S. , title =. Proceedings of the 2005 ACM SIGCOMM Workshop on Mining Network Data , pages =. 2005 , isbn =. doi:10.1145/1080173.1080176 , abstract =

work page doi:10.1145/1080173.1080176 2005
[11]

Buriol, Luciana and Leonardi, Stefano and Donato, Debora and Matzner, Tobias , year =

work page
[12]

2021 , eprint=

Truly Perfect Samplers for Data Streams and Sliding Windows , author=. 2021 , eprint=

work page 2021
[13]

Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages =

Cohen, Edith , title =. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages =. 2015 , isbn =. doi:10.1145/2783258.2783279 , abstract =

work page doi:10.1145/2783258.2783279 2015
[14]

The Space Complexity of Approximating the Frequency Moments , journal =

Noga Alon and Yossi Matias and Mario Szegedy , abstract =. The Space Complexity of Approximating the Frequency Moments , journal =. 1999 , issn =. doi:https://doi.org/10.1006/jcss.1997.1545 , url =

work page doi:10.1006/jcss.1997.1545 1999
[15]

Probabilistic Counting Algorithms for Data Base Applications , journal =

Philippe Flajolet and G. Probabilistic Counting Algorithms for Data Base Applications , journal =. 1985 , issn =. doi:https://doi.org/10.1016/0022-0000(85)90041-8 , url =

work page doi:10.1016/0022-0000(85)90041-8 1985
[16]

2010 , eprint=

Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems , author=. 2010 , eprint=

work page 2010
[17]

2019 , eprint=

Perfect L_p Sampling in a Data Stream , author=. 2019 , eprint=

work page 2019
[18]

Fernandez, prefix=de la, useprefix=true and Kannan, Ravi and Karpinski, Marek , date =

Alon, Noga and family=Vega, given=W. Fernandez, prefix=de la, useprefix=true and Kannan, Ravi and Karpinski, Marek , date =. Random Sampling and Approximation of. doi:10.1016/S0022-0000(03)00008-4 , note =

work page doi:10.1016/s0022-0000(03)00008-4
[19]

Ahn, Kook Jin and Guha, Sudipto , editor =. Graph. Automata,. doi:10.1007/978-3-642-02930-1_27 , eventdate =

work page doi:10.1007/978-3-642-02930-1_27
[20]

doi:10.1006/jcss.1998.1605 , title =

Arora, Sanjeev and Karger, David and Karpinski, Marek , date =. doi:10.1006/jcss.1998.1605 , title =

work page doi:10.1006/jcss.1998.1605 1998
[21]

doi:10.1007/s00778-013-0340-z , url =

Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-Time Story Identification , author =. doi:10.1007/s00778-013-0340-z , url =

work page doi:10.1007/s00778-013-0340-z
[22]

Monochromatic Triangles, Triangle Listing and

Assadi, Sepehr and Kol, Gillat and Saxena, Raghuvansh R. and Yu, Huacheng , date =. Multi-. 2020. doi:10.1109/FOCS46700.2020.00041 , eventdate =

work page doi:10.1109/focs46700.2020.00041 2020
[23]

doi:10.1145/278298.278306 , note =

Proof Verification and the Hardness of Approximation Problems , author =. doi:10.1145/278298.278306 , note =

work page doi:10.1145/278298.278306
[24]

Explicit

Alon, Noga , date =. Explicit. doi:10.1007/s00493-020-4429-x , langid =

work page doi:10.1007/s00493-020-4429-x
[25]

A framework for dynamic matching in weighted graphs , booktitle =

Assadi, Sepehr and N, Vishvajeet , date =. Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming. Proceedings of the 53rd. doi:10.1145/3406325.3451110 , eventdate =

work page doi:10.1145/3406325.3451110
[26]

Sublinear

Bhaskara, Aditya and Daruki, Samira and Venkatasubramanian, Suresh , namea =. Sublinear. 45th. doi:10.4230/LIPICS.ICALP.2018.16 , eventdate =

work page doi:10.4230/lipics.icalp.2018.16 2018
[27]

Subsampling Mathematical Relaxations and Average-Case Complexity , booktitle =

Barak, Boaz and Hardt, Moritz and Holenstein, Thomas and Steurer, David , date =. Subsampling Mathematical Relaxations and Average-Case Complexity , booktitle =. doi:10.5555/2133036.2133077 , eventdate =

work page doi:10.5555/2133036.2133077
[28]

Space- and

Bhattacharya, Sayan and Henzinger, Monika and Nanongkai, Danupon and Tsourakakis, Charalampos , date =. Space- and. Proceedings of the. doi:10.1145/2746539.2746592 , eventdate =

work page doi:10.1145/2746539.2746592
[29]

On Sketching Approximations for Symmetric

Boyland, Joanna and Hwang, Michael and Prasad, Tarun and Singer, Noah and Velusamy, Santhoshini , editor =. On Sketching Approximations for Symmetric. Approximation,. doi:10.4230/LIPIcs.APPROX/RANDOM.2022.38 , eventdate =

work page doi:10.4230/lipics.approx/random.2022.38 2022
[30]

Densest Subgraph in Streaming and

Bahmani, Bahman and Kumar, Ravi and Vassilvitskii, Sergei , date =. Densest Subgraph in Streaming and. Proceedings of the 38th. doi:10.14778/2140436.2140442 , eventdate =

work page doi:10.14778/2140436.2140442
[31]

doi:10.1007/BF01180606 , langid =

Zur Verallgemeinerung des Bertrandschen Postulates, daß zwischen x und 2x stets Primzahlen liegen , author =. doi:10.1007/BF01180606 , langid =

work page doi:10.1007/bf01180606
[32]

Chou, Chi-Ning and Golovnev, Alexander and Sudan, Madhu and Velingker, Ameya and Velusamy, Santhoshini , date =. Linear. Proceedings of the 54th. doi:10.1145/3519935.3519983 , eventdate =

work page doi:10.1145/3519935.3519983
[33]

Sketching

Chou, Chi-Ning and Golovnev, Alexander and Shahrasbi, Amirbehshad and Sudan, Madhu and Velusamy, Santhoshini , editor =. Sketching. Approximation,. doi:10.4230/LIPIcs.APPROX/RANDOM.2022.35 , eventdate =

work page doi:10.4230/lipics.approx/random.2022.35 2022
[34]

Approximability of All

Chou, Chi-Ning and Golovnev, Alexander and Sudan, Madhu and Velusamy, Santhoshini , date =. Approximability of All. 2102.12351v7 , eprinttype =

work page arXiv
[35]

Sketching

Chou, Chi-Ning and Golovnev, Alexander and Sudan, Madhu and Velusamy, Santhoshini , date =. Sketching. doi:10.1145/3649435 , note =

work page doi:10.1145/3649435
[36]

Chou, Chi-Ning and Golovnev, Alexander and Velusamy, Santhoshini , date =. Optimal. 2020. doi:10.1109/FOCS46700.2020.00039 , eventdate =

work page doi:10.1109/focs46700.2020.00039 2020
[37]

Charikar, Moses , editor =. Greedy. Approximation. doi:10.1007/3-540-44436-X_10 , eventdate =

work page doi:10.1007/3-540-44436-x_10
[38]

Chen, Lijie and Kol, Gillat and Paramonov, Dmitry and Saxena, Raghuvansh and Song, Zhao and Yu, Huacheng , date =. Towards. Proceedings of the 2023. doi:10.1137/1.9781611977554.ch35 , eventdate =

work page doi:10.1137/1.9781611977554.ch35 2023
[39]

, date =

Esfandiari, Hossein and Hajiaghayi, MohammadTaghi and Woodruff, David P. , date =. Brief. Proceedings of the 28th. doi:10.1145/2935764.2935813 , eventdate =

work page doi:10.1145/2935764.2935813
[40]

, date =

Fernandez de la Vega, W. , date =. doi:10.1002/(SICI)1098-2418(199605)8:3<187::AID-RSA3>3.0.CO;2-U , langid =

work page doi:10.1002/(sici)1098-2418(199605)8:3
[41]

Fakcharoenphol, Jittat and Vajanopath, Phanu , date =. 19th. doi:10.1109/JCSSE54890.2022.9836261 , eventdate =

work page doi:10.1109/jcsse54890.2022.9836261 2022
[42]

and Tarjan, Robert E

Gallo, Giorgio and Grigoriadis, Michael D. and Tarjan, Robert E. , date =. A

work page
[43]

and Manohar, Peter , date =

Guruswami, Venkatesan and Kothari, Pravesh K. and Manohar, Peter , date =. Algorithms and. Proceedings of the 54th. doi:10.1145/3519935.3519955 , eventdate =

work page doi:10.1145/3519935.3519955
[44]

Streaming

Guruswami, Venkatesan and Tao, Runzhou , editor =. Streaming. Approximation,. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.5 , eventdate =

work page doi:10.4230/lipics.approx-random.2019.5 2019
[45]

Streaming

Guruswami, Venkatesan and Velingker, Ameya and Velusamy, Santhoshini , editor =. Streaming. Approximation, Randomization, and Combinatorial Optimization. doi:10.4230/LIPIcs.APPROX-RANDOM.2017.8 , eventdate =

work page doi:10.4230/lipics.approx-random.2017.8 2017
[46]

Sketching Cuts in Graphs and Hypergraphs , booktitle =

Kogan, Dmitry and Krauthgamer, Robert , date =. Sketching Cuts in Graphs and Hypergraphs , booktitle =. doi:10.1145/2688073.2688093 , eventdate =

work page doi:10.1145/2688073.2688093
[47]

Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

Kapralov, Michael and Krachun, Dmitry , date =. An Optimal Space Lower Bound for Approximating. Proceedings of the 51st. doi:10.1145/3313276.3316364 , eventdate =

work page doi:10.1145/3313276.3316364
[48]

Streaming Lower Bounds for Approximating

Kapralov, Michael and Khanna, Sanjeev and Sudan, Madhu , date =. Streaming Lower Bounds for Approximating. Proceedings of the 26th. doi:10.1137/1.9781611973730.84 , eventdate =

work page doi:10.1137/1.9781611973730.84
[49]

Proceedings of the 28th

Kapralov, Michael and Khanna, Sanjeev and Sudan, Madhu and Velingker, Ameya , date =. Proceedings of the 28th. doi:10.5555/3039686.3039798 , eventdate =

work page doi:10.5555/3039686.3039798
[50]

Kallaugher, John and Parekh, Ojas , date =. The. 2022. doi:10.1109/FOCS54457.2022.00054 , eventdate =

work page doi:10.1109/focs54457.2022.00054 2022
[51]

and Yu, Huacheng , editor =

Kol, Gillat and Paramonov, Dmitry and Saxena, Raghuvansh R. and Yu, Huacheng , editor =. Characterizing the. 14th. doi:10.4230/LIPIcs.ITCS.2023.80 , eventdate =

work page doi:10.4230/lipics.itcs.2023.80 2023
[52]

Lanciano, Tommaso and Miyauchi, Atsushi and Fazzone, Adriano and Bonchi, Francesco , date =. A. doi:10.1145/3653298 , url =

work page doi:10.1145/3653298
[53]

Mathieu, Claire and family=Rougemont, given=Michel, prefix=de, useprefix=true , date =. Large. Proceedings of the 2020. doi:10.1145/3412815.3416884 , eventdate =

work page doi:10.1145/3412815.3416884 2020
[54]

Mitrovic, Slobodan and Pan, Theodore , date =. Faster. Proceedings of the 41st. doi:10.5555/3692070.3693532 , eventdate =

work page doi:10.5555/3692070.3693532
[55]

Yet Another Algorithm for Dense Max Cut: Go Greedy , booktitle =

Mathieu, Claire and Schudy, Warren , date =. Yet Another Algorithm for Dense Max Cut: Go Greedy , booktitle =. doi:10.5555/1347082.1347102 , eventtitle =

work page doi:10.5555/1347082.1347102
[56]

The Theory of Error Correcting Codes , author =

work page
[57]

, editor =

McGregor, Andrew and Tench, David and Vorotnikova, Sofya and Vu, Hoa T. , editor =. Densest. Mathematical. doi:10.1007/978-3-662-48054-0_39 , eventdate =

work page doi:10.1007/978-3-662-48054-0_39
[58]

, date =

Monemizadeh, Morteza and Woodruff, David P. , date =. 1-. Proceedings of the. doi:10.1137/1.9781611973075.92 , eventtitle =

work page doi:10.1137/1.9781611973075.92
[59]

Strongly Refuting Random

Raghavendra, Prasad and Rao, Satish and Schramm, Tselil , date =. Strongly Refuting Random. Proceedings of the 49th. doi:10.1145/3055399.3055417 , eventdate =

work page doi:10.1145/3055399.3055417
[60]

On Streaming Approximation Algorithms for Constraint Satisfaction Problems , author =

work page
[61]

, editor =

Singer, Noah G. , editor =. Oblivious Algorithms for the. Approximation,. doi:10.4230/LIPIcs.APPROX/RANDOM.2023.15 , eventdate =

work page doi:10.4230/lipics.approx/random.2023.15 2023
[62]

and Li, Jerry and Liu, Allen and Narayanan, Shyam , booktitle =

Saxena, Raghuvansh R. and Singer, Noah and Sudan, Madhu and Velusamy, Santhoshini , date =. Improved Streaming Algorithms for. 63rd. doi:10.1109/FOCS57990.2023.00055 , eventdate =

work page doi:10.1109/focs57990.2023.00055 2023
[63]

and Singer, Noah G

Saxena, Raghuvansh R. and Singer, Noah G. and Sudan, Madhu and Velusamy, Santhoshini , date =. Streaming Complexity of. Proceedings of the 2023. doi:10.1137/1.9781611977554.ch156 , eventdate =

work page doi:10.1137/1.9781611977554.ch156 2023
[64]

and Sudan, Madhu and Velusamy, Santhoshini , date =

Saxena, Raghuvansh and Singer, Noah G. and Sudan, Madhu and Velusamy, Santhoshini , date =. Streaming. Proceedings of the 2025. doi:10.1137/1.9781611978322.111 , eventdate =

work page doi:10.1137/1.9781611978322.111 2025
[65]

Streaming Approximation Resistance of Every Ordering

Singer, Noah and Sudan, Madhu and Velusamy, Santhoshini , date =. Streaming Approximation Resistance of Every Ordering. doi:10.1007/s00037-024-00252-5 , keywords =

work page doi:10.1007/s00037-024-00252-5
[66]

Streaming and

Sudan, Madhu , editor =. Streaming and. 49th. doi:10.4230/LIPIcs.ICALP.2022.5 , eventdate =

work page doi:10.4230/lipics.icalp.2022.5 2022
[67]

, editor =

Sun, Xiaoming and Woodruff, David P. , editor =. Tight. Approximation,. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.435 , eventdate =

work page doi:10.4230/lipics.approx-random.2015.435 2015
[68]

Pseudorandomness , author =

work page
[69]

Random Sampling with a Reservoir , author =

work page
[70]

Probabilistic Computations:

Yao, Andrew Chi-Chih , date =. Probabilistic Computations:. Proceedings of the 18th. doi:10.1109/SFCS.1977.24 , eventdate =

work page doi:10.1109/sfcs.1977.24 1977
[71]

Algorithms for Streaming Graphs , author =

work page
[72]

Azarmehr, Amir and Behnezhad, Soheil and Ferrante, Shane and Saneian, Mohammad , year = 2025, month = dec, eprint =. Half-

work page 2025
[73]

Fei, Yumou and Minzer, Dor and Wang, Shuo , year = 2025, month = dec, publisher =. Multi-. Proceedings of the 66th

work page 2025
[74]

Fei, Yumou and Minzer, Dor and Wang, Shuo , year = 2026, publisher =. A. Proceedings of the 58th

work page 2026