Pith. sign in

REVIEW 1 major objections 2 minor 73 references

Streaming Complexity Separations for Dense and Sparse Graphs

T0 review · 1 major / 2 minor · reviewed 2026-05-12 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Streaming max-cut requires linear space to output an approximate cut in dense graphs but an extra log factor in sparser graphs.

desk verdict 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 →

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

Yang P. Liu , Hoai-An Nguyen , Noah G. Singer , David P. Woodruff This is my paper · ORCID
classification cs.DScs.CC
keywords streamingalgorithmsmaximumcutspacecomplexitydensegraphssparsedensestsubgraphapproximationcommunication
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 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.

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.

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.

Watch

Extended reading notes

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.

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.

Editorial extensions

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.

Reading between the lines

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

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

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

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)
  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)
  1. [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.
  2. 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

  1. 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 · score 0.0 of 10

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.

Assumptions & free parameters 0 free parameters · 2 assumptions · 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.

assumptions (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

how reviews work

0 comments
Cite this review

Pith. "Pith review of Streaming Complexity Separations for Dense and Sparse Graphs." pith.science (2026). https://pith.science/paper/2605.09814

@misc{pith2026260509814,
  author       = {Pith},
  title        = {Pith review of: Streaming Complexity Separations for Dense and Sparse Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2605.09814}},
  note         = {Machine review of arXiv:2605.09814}
}
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.

Figures

Figures reproduced from arXiv: 2605.09814 by the authors.

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 ∩ T are larg… 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 Densest-Subgraph… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

73 extracted references · 73 canonical work pages

  1. [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

  2. [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

  3. [4]

    Identifying and Filtering Near-Duplicate Documents

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

    work page 2000

  4. [5]

    Journal of Computer and System Sciences55(3), 441– 453 (1997)

    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

  5. [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

  6. [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

  7. [8]

    2023 , eprint=

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

    work page 2023

  8. [9]

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

    work page

Show all 73 references
  1. [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 =

    2005 doi

  2. [11]

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

  3. [12]

    2021 , eprint=

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

    2021

  4. [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 =

    2015 doi

  5. [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 =

    1999 doi

  6. [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 =

    1985 doi

  7. [16]

    2010 , eprint=

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

    2010

  8. [17]

    2019 , eprint=

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

    2019

  9. [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 =

    doi

  10. [19]

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

    doi

  11. [20]

    doi:10.1006/jcss.1998.1605 , title =

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

    1998 doi

  12. [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 =

    doi

  13. [22]

    and Yu, Huacheng , date =

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

    2020 doi

  14. [23]

    doi:10.1145/278298.278306 , note =

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

    doi

  15. [24]

    Explicit

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

    doi

  16. [25]

    Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming

    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 =

    doi

  17. [26]

    Sublinear

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

    2018 doi

  18. [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 =

    doi

  19. [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 =

    doi

  20. [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 =

    2022 doi

  21. [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 =

    doi

  22. [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 =

    doi

  23. [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 =

    doi

  24. [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 =

    2022 doi

  25. [34]

    Approximability of All

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

  26. [35]

    Sketching

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

    doi

  27. [36]

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

    2020 doi

  28. [37]

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

    doi

  29. [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 =

    2023 doi

  30. [39]

    , date =

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

    doi

  31. [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 =

    doi

  32. [41]

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

    2022 doi

  33. [42]

    and Tarjan, Robert E

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

  34. [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 =

    doi

  35. [44]

    Streaming

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

    2019 doi

  36. [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 =

    2017 doi

  37. [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 =

    doi

  38. [47]

    An Optimal Space Lower Bound for Approximating

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

    doi

  39. [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 =

    doi

  40. [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 =

    doi

  41. [50]

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

    2022 doi

  42. [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 =

    2023 doi

  43. [52]

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

    doi

  44. [53]

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

    2020 doi

  45. [54]

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

    doi

  46. [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 =

    doi

  47. [56]

    The Theory of Error Correcting Codes , author =

  48. [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 =

    doi

  49. [58]

    , date =

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

    doi

  50. [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 =

    doi

  51. [60]

    On Streaming Approximation Algorithms for Constraint Satisfaction Problems , author =

  52. [61]

    , editor =

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

    2023 doi

  53. [62]

    and Singer, Noah and Sudan, Madhu and Velusamy, Santhoshini , date =

    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 =

    2023 doi

  54. [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 =

    2023 doi

  55. [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 =

    2025 doi

  56. [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 =

    doi

  57. [66]

    Streaming and

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

    2022 doi

  58. [67]

    , editor =

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

    2015 doi

  59. [68]

    Pseudorandomness , author =

  60. [69]

    Random Sampling with a Reservoir , author =

  61. [70]

    Probabilistic Computations:

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

    1977 doi

  62. [71]

    Algorithms for Streaming Graphs , author =

  63. [72]

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

    2025

  64. [73]

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

    2025

  65. [74]

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

    2026

Pith tools

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