pith. sign in

arxiv: 2512.19521 · v2 · submitted 2025-12-22 · 💻 cs.DS

Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes

Santhoshini Velusamy This is my paper

Pith reviewed 2026-05-16 20:18 UTC · model grok-4.3

classification 💻 cs.DS
keywords Max-DICUTstreaming algorithmsapproximation algorithmssublinear spacetwo-pass algorithmsconstraint satisfaction problems
0
0 comments X

The pith

Two passes achieve (1/2 - ε) approximation for Max-DICUT on arbitrary graphs in sublinear space.

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

The paper gives a two-pass streaming algorithm for Max-DICUT that reaches (1/2 - ε) approximation in sublinear space for every constant ε > 0, even when graphs have unbounded degree. Earlier work proved that no single-pass algorithm can exceed 1/2 approximation and that unbounded-degree graphs required more passes. The result narrows the gap between known lower bounds and achievable approximations in the streaming model for this canonical CSP. A sympathetic reader cares because it reduces the number of passes needed while preserving near-optimal guarantees and sublinear space.

Core claim

We give a two-pass algorithm that achieves (1/2−ε)-approximation in sublinear space, for every constant ε>0, on arbitrary graphs of unbounded degree.

What carries the argument

A two-pass procedure that samples and sketches edges from the stream with random access to produce the approximation guarantee while using only sublinear space.

Load-bearing premise

The standard two-pass streaming model with random access to the edge stream and sublinear space suffices to implement the required sampling or sketching steps for arbitrary graphs.

What would settle it

A concrete graph on which the two-pass algorithm fails to reach (1/2 - ε) approximation despite using only sublinear space.

read the original abstract

The Max-DICUT problem has gained a lot of attention in the streaming setting in recent years, and has so far served as a canonical problem for designing algorithms for general constraint satisfaction problems (CSPs) in this setting. A seminal result of Kapralov and Krachun [STOC 2019] shows that it is impossible to beat $1/2$-approximation for Max-DICUT in sublinear space in the single-pass streaming setting, even on bounded-degree graphs. In a recent work, Saxena, Singer, Sudan, and Velusamy [SODA 2025] prove that the above lower bound is tight by giving a single-pass algorithm for bounded-degree graphs that achieves $(1/2-\epsilon)$-approximation in sublinear space, for every constant $\epsilon>0$. For arbitrary graphs of unbounded degree, they give an $O(1/\epsilon)$-pass $O(\log n)$ space algorithm. Their work left open the question of obtaining $1/2$-approximation for arbitrary graphs in the single-pass setting in sublinear space. We make progress towards this question and give a two-pass algorithm that achieves $(1/2-\epsilon)$-approximation in sublinear space, for every constant $\epsilon>0$.

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.

Referee Report

0 major / 3 minor

Summary. The manuscript presents a two-pass streaming algorithm for Max-DICUT that achieves a (1/2−ε)-approximation in sublinear space (specifically O(ε^{-2} log n)) for arbitrary graphs of unbounded degree, for every constant ε>0. It builds on the single-pass (1/2−ε) result of Saxena et al. for bounded-degree graphs and the O(1/ε)-pass O(log n)-space result for unbounded-degree graphs, using a first-pass degree-oblivious sketch based on random edge sampling and a second-pass verification, with a charging argument to handle high-degree vertices.

Significance. If the analysis holds, the result meaningfully advances streaming algorithms for CSPs by reducing pass complexity to a constant (two) while preserving sublinear space and near-optimal approximation on general graphs. The degree-oblivious sketch and charging argument that isolates high-degree contributions without explicit storage constitute a clear technical contribution, directly addressing the open question left by prior work on single-pass sublinear-space algorithms for unbounded-degree Max-DICUT.

minor comments (3)
  1. [Section 4] Section 4: the space bound is stated as O(ε^{-2} log n) independent of maximum degree; explicitly deriving the hidden constants or providing a concrete expression for the sampling probability (inversely proportional to the global threshold) would strengthen the presentation.
  2. [Section 5] Section 5: the charging argument for isolating high-degree vertex contributions is load-bearing for the unbounded-degree claim; adding a brief illustrative example or diagram showing how the reduction to the bounded-degree case proceeds would improve readability without altering the proof.
  3. [Abstract/Introduction] The abstract and introduction could include a one-sentence pointer to the key technical ingredients (degree-oblivious sketch + charging) to help readers quickly locate the novelty relative to Saxena et al.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and for recommending minor revision. The referee's summary correctly captures the main contributions of our two-pass algorithm, including the degree-oblivious sketch and the charging argument for handling high-degree vertices.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents a new two-pass streaming algorithm for Max-DICUT on unbounded-degree graphs, achieving (1/2-ε)-approximation in sublinear space. The construction uses a first-pass degree-oblivious sketch and second-pass verification with a charging argument to handle high-degree vertices. This is independent of any fitted parameters or self-definitional reductions. The citation to prior work provides background but the main result does not reduce to it by construction. The space bound O(ε^{-2} log n) is derived directly from the sketch size analysis.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The result rests on the standard streaming model and the existence of a new algorithmic construction whose details are not visible in the abstract.

free parameters (1)
  • ε
    Arbitrary positive constant controlling the approximation gap; appears in the guarantee statement.
axioms (1)
  • domain assumption Standard two-pass streaming model with sublinear space
    Invoked implicitly when claiming the algorithm works in the streaming setting.

pith-pipeline@v0.9.0 · 5527 in / 1172 out tokens · 19759 ms · 2026-05-16T20:18:03.795713+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs

    cs.CC 2026-04 unverdicted novelty 8.0

    Tight single-pass linear-space lower bounds for approximating arbitrary Max-CSP(F) whenever the basic LP admits a (γ,β)-integrality gap.

  2. Near-Optimal Space Lower Bounds for Streaming CSPs

    cs.CC 2026-04 unverdicted novelty 8.0

    Near-optimal space lower bounds of Ω(√n/p) are established for (α_LP + ε)-approximations in streaming CSPs, improving prior Ω(n^{1/3}/p) bounds via Fourier analysis.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages · cited by 2 Pith papers

  1. [1]

    Beating Two-Thirds For Random-Order Streaming Matching

    [AB21] Sepehr Assadi and Soheil Behnezhad. “Beating Two-Thirds For Random-Order Streaming Matching”. In:48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference). Ed. by Nikhil Bansal, Emanuela Merelli, and James Worrell. Vol

    work page 2021

  2. [2]

    Graph Sparsification in the Semi-Streaming Model

    LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2021, 19:1–19:13.doi:10.4230/LIPICS.ICALP.2021.19.url:https://doi. org/10.4230/LIPIcs.ICALP.2021.19. [AG09] Kook Jin Ahn and Sudipto Guha. “Graph Sparsification in the Semi-Streaming Model”. In: Proceedings of the 36th Internatilonal Collogquium on Automata, Languages and Programming: Part II. I...

    work page doi:10.4230/lipics.icalp.2021.19.url:https://doi 2021

  3. [3]

    Random sampling and approximation of MAX-CSPs

    Ed. by Samir Khuller and Virginia Vassilevska Williams. ACM, 2021, pp. 612–625.doi:10.1145/3406325. 3451110.url:https://doi.org/10.1145/3406325.3451110. [AVKK03] Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, and Marek Karpinski. “Random sampling and approximation of MAX-CSPs”. In:J. Comput. Syst. Sci.67.2 (2003), pp. 212– 243.doi:10 . 1016 / S00...

    work page doi:10.1145/3406325 2021

  4. [4]

    Improved Bounds for Matching in Random-Order Streams

    LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2018, 16:1–16:14.doi:10.4230/ LIPICS.ICALP.2018.16.url:https://doi.org/10.4230/LIPIcs.ICALP.2018.16. [Ber24] Aaron Bernstein. “Improved Bounds for Matching in Random-Order Streams”. In:Theory Comput. Syst.68.4 (2024), pp. 758–772.doi:10.1007/S00224- 023- 10155- 7.url:https: //doi.org/10.1007/s00...

    work page doi:10.4230/lipics.icalp.2018.16 2018

  5. [5]

    Revisiting Fre- quency Moment Estimation in Random Order Streams

    Ed. by Dana Randall. SIAM, 2011, pp. 512–531.doi:10 . 1137 / 1 . 9781611973082.41.url:https://doi.org/10.1137/1.9781611973082.41. [BVWY18] Vladimir Braverman, Emanuele Viola, David P. Woodruff, and Lin F. Yang. “Revisiting Fre- quency Moment Estimation in Random Order Streams”. In:45th International Colloquium on Automata, Languages, and Programming, ICAL...

    work page doi:10.1137/1.9781611973082.41 2011

  6. [6]

    Vertex Order- ing Problems in Directed Graph Streams

    LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2018, 25:1–25:14.doi: 10.4230/LIPICS.ICALP.2018.25.url:https://doi.org/10.4230/LIPIcs.ICALP.2018.25. 24 [CGMV20] Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, and Sofya Vorotnikova. “Vertex Order- ing Problems in Directed Graph Streams”. In:Proceedings of the 2020 ACM-SIAM Symposium on Discr...

    work page doi:10.4230/lipics.icalp.2018.25.url:https://doi.org/10.4230/lipics.icalp.2018.25 2018

  7. [7]

    Linear space streaming lower bounds for approximating CSPs

    Ed. by Shuchi Chawla. SIAM, 2020, pp. 1786–1802.doi:10 . 1137 / 1 . 9781611975994 . 109.url: https://doi.org/10.1137/1.9781611975994.109. [CGS+22] Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy. “Linear space streaming lower bounds for approximating CSPs”. In:STOC ’22: 54th Annual ACM SIGACT Symposium on Theory o...

    work page doi:10.1137/1.9781611975994.109 2020

  8. [8]

    by Stefano Leonardi and Anupam Gupta

    Ed. by Stefano Leonardi and Anupam Gupta. ACM, 2022, pp. 275–288.doi:10.1145/ 3519935.3519983.url:https://doi.org/10.1145/3519935.3519983. [CGSV22] Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy.Approxima- bility of all Boolean CSPs with linear sketches

    work page doi:10.1145/3519935.3519983 2022

  9. [9]

    Sketching Approximability of All Finite CSPs

    arXiv:2102.12351 [cs.CC].url:https: //arxiv.org/abs/2102.12351. [CGSV24] Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. “Sketching Approximability of All Finite CSPs”. In:J. ACM71.2 (2024), 15:1–15:74.doi:10 . 1145 / 3649435.url:https://doi.org/10.1145/3649435. [CGV20] Chi-Ning Chou, Alexander Golovnev, and Santhoshini Velusamy....

    work page doi:10.1145/3649435 2024

  10. [10]

    Stochastic Weighted Matching: (1-

    Ed. by Sandy Irani. IEEE, 2020, pp. 330–341.doi:10.1109/FOCS46700.2020.00039.url: https://doi.org/10.1109/FOCS46700.2020.00039. [CLS17] Keren Censor-Hillel, Rina Levy, and Hadas Shachnai. “Fast Distributed Approximation for Max-Cut”. In:Algorithms for Sensor Systems - 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks,...

    work page doi:10.1109/focs46700.2020.00039.url: 2020

  11. [11]

    Multi-Pass Streaming Lower Bounds for Approx- imating Max-Cut

    arXiv:2509.11399 [cs.CC].url:https://arxiv.org/abs/2509.11399. [FMW25b] Yumou Fei, Dor Minzer, and Shuo Wang. “Multi-Pass Streaming Lower Bounds for Approx- imating Max-Cut”. In:CoRRabs/2503.23404 (2025).doi:10 . 48550 / ARXIV . 2503 . 23404. arXiv:2503.23404.url:https://doi.org/10.48550/arXiv.2503.23404. [FS02] Uriel Feige and Gideon Schechtman. “On the ...

    work page doi:10.48550/arxiv.2503.23404 2025

  12. [12]

    Improved Approximation Algorithms for Max- imum Cut and Satisfiability Problems Using Semidefinite Programming

    LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2017, 8:1–8:19.doi:10 . 4230 / LIPICS . APPROX - RANDOM . 2017 . 8.url:https : //doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.8. [GW95] Michel X. Goemans and David P. Williamson. “Improved Approximation Algorithms for Max- imum Cut and Satisfiability Problems Using Semidefinite Programming”. In:J. ...

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

  13. [13]

    Gily \'e n , author Y

    Ed. by Moses Charikar and Edith Cohen. ACM, 2019, pp. 277–288.doi:10.1145/3313276.3316364.url:https://doi. org/10.1145/3313276.3316364. [KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. “Optimal Inapprox- imability Results for MAX-CUT and Other 2-Variable CSPs?” In:SIAM J. Comput.37.1 (2007), pp. 319–357.doi:10.1137/S009753970544737...

    work page doi:10.1145/3313276.3316364.url:https://doi 2019

  14. [14]

    (1 + Ω(1))- Approximation to MAX-CUT Requires Linear Space

    Ed. by Pi- otr Indyk. SIAM, 2015, pp. 1263–1282.doi:10 . 1137 / 1 . 9781611973730 . 84.url:https : //doi.org/10.1137/1.9781611973730.84. [KKSV17] Michael Kapralov, Sanjeev Khanna, Madhu Sudan, and Ameya Velingker. “(1 + Ω(1))- Approximation to MAX-CUT Requires Linear Space”. In:Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorit...

    work page doi:10.1137/1.9781611973730.84 2015

  15. [15]

    Testable Bounded Degree Graph Properties Are Random Order Streamable

    LIPIcs. Schloss Dagstuhl - Leibniz- Zentrum f¨ ur Informatik, 2023, 80:1–80:15.doi:10.4230/LIPICS.ITCS.2023.80.url:https: //doi.org/10.4230/LIPIcs.ITCS.2023.80. [MMPS17] Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, and Christian Sohler. “Testable Bounded Degree Graph Properties Are Random Order Streamable”. In:44th International Colloquium on Automata...

    work page doi:10.4230/lipics.itcs.2023.80.url:https: 2023

  16. [16]

    23 Sergey Goncharov, Stefan Milius, Lutz Schröder, Stelios Tsampas, and Henning Urbat

    LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2017, 131:1–131:14.doi:10.4230/LIPICS. ICALP.2017.131.url:https://doi.org/10.4230/LIPIcs.ICALP.2017.131. [MS08] Claire Mathieu and Warren Schudy. “Yet another algorithm for dense max cut: go greedy”. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, S...

    work page doi:10.4230/lipics 2017

  17. [17]

    Estimating Graph Parameters from Random Order Streams

    Ed. by Shang-Hua Teng. SIAM, 2008, pp. 176–182.url:http://dl.acm.org/citation.cfm?id=1347082.1347102. [PS18] 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, SODA 2018, New Orleans, LA, USA, January 7-10,

    work page arXiv 2008

  18. [18]

    Optimal algorithms and inapproximability results for every CSP?

    Ed. by Artur Czumaj. SIAM, 2018, pp. 2449–2466.doi:10.1137/1.9781611975031.157.url:https://doi.org/10.1137/1. 9781611975031.157. [Rag08] Prasad Raghavendra. “Optimal algorithms and inapproximability results for every CSP?” In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20,

    work page doi:10.1137/1.9781611975031.157.url:https://doi.org/10.1137/1 2018

  19. [19]

    Optimal algorithms and inapproximability results for every CSP? , booktitle =

    Ed. by Cynthia Dwork. ACM, 2008, pp. 245–254.doi: 10.1145/1374376.1374414.url:https://doi.org/10.1145/1374376.1374414. [SSSV23a] Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, and Santhoshini Velusamy. “Streaming complexity of CSPs with randomly ordered constraints”. In:Proceedings of the 2023 ACM- SIAM Symposium on Discrete Algorithms, SODA 2023, Floren...

    work page doi:10.1145/1374376.1374414.url:https://doi.org/10.1145/1374376.1374414 2008

  20. [20]

    Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots

    Ed. by Nikhil Bansal and Viswanath Nagarajan. SIAM, 2023, pp. 4083–4103.doi:10.1137/ 1.9781611977554.CH156.url:https://doi.org/10.1137/1.9781611977554.ch156. 26 [SSSV23b] Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, and Santhoshini Velusamy. “Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots”. In:64th IEEE Annual Symposiu...

    work page doi:10.1137/1.9781611977554.ch156 2023

  21. [21]

    Kothari and Santosh S

    IEEE, 2023, pp. 855–870.doi:10.1109/FOCS57990.2023.00055.url: https://doi.org/10.1109/FOCS57990.2023.00055. [SSSV25] Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, and Santhoshini Velusamy. “Streaming Algorithms via Local Algorithms for Maximum Directed Cut”. In:Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New O...

    work page doi:10.1109/focs57990.2023.00055.url: 2023

  22. [22]

    by Yossi Azar and Debmalya Panigrahi

    Ed. by Yossi Azar and Debmalya Panigrahi. SIAM, 2025, pp. 3392–3408. doi:10.1137/1.9781611978322.111.url:https://doi.org/10.1137/1.9781611978322

    work page doi:10.1137/1.9781611978322.111.url:https://doi.org/10.1137/1.9781611978322 2025

  23. [23]

    Non-approximability results for optimization problems on bounded degree instances

    arXiv:2509.17926 [cs.CC].url:https: //arxiv.org/abs/2509.17926. [Tre01] Luca Trevisan. “Non-approximability results for optimization problems on bounded degree instances”. In:Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece. Ed. by Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis. ACM,...

    work page doi:10.1145/380752.380839.url:https://doi.org/ 2001

  24. [24]

    Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems , booktitle =

    Ed. by Michael Mitzenmacher. ACM, 2009, pp. 263–272.doi:10.1145/1536414.1536452.url: https://doi.org/10.1145/1536414.1536452. [VY25] Santhoshini Velusamy and Huacheng Yu.Optimal streaming algorithm for detectingℓ 2 heavy hitters in random order streams

    work page doi:10.1145/1536414.1536452.url: 2009

  25. [25]

    Optimal Constant-Time Approximation Algorithms and (Unconditional) In- approximability Results for Every Bounded-Degree CSP

    arXiv:2509.07286 [cs.DS].url:https://arxiv. org/abs/2509.07286. [Yos11] Yuichi Yoshida. “Optimal Constant-Time Approximation Algorithms and (Unconditional) In- approximability Results for Every Bounded-Degree CSP”. In:Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing. STOC 2011 (San Jose, CA, USA, June 6– 8, 2011). Association for...

    work page arXiv 2011