pith. machine review for the scientific record. sign in

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

Recognition: 2 theorem links

· Lean Theorem

Computing Flows in Subquadratic Space

Albert Weng, Jan van den Brand, Zhao Song

Pith reviewed 2026-05-12 01:51 UTC · model grok-4.3

classification 💻 cs.DS
keywords streaming algorithmsminimum cost flowsubquadratic spaceapproximate flowscommunication complexityspace complexitymaximum flow
0
0 comments X

The pith

A streaming algorithm computes approximate minimum-cost flows using subquadratic space by reporting each edge's flow value as it appears in the final pass.

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

The paper establishes that minimum-cost flow on directed graphs need not require quadratic space to output the flow on every edge. By designing an algorithm that uses roughly n to the 1.5 times logarithmic factors in space and square root n passes, and that reports the approximate flow on an edge exactly when that edge is read during the last pass, the work bypasses existing lower bounds that assumed the full flow vector must be stored simultaneously. This result applies when capacities and costs are integers bounded by W and the approximation is additive within ε. A sympathetic reader cares because it shows that space barriers for solution output in streaming models are not as absolute as prior quadratic lower bounds suggested, with direct consequences for related models like communication complexity.

Core claim

For a directed graph with integer capacities and costs bounded by W, we provide a Õ(n^{1.5} log(W/ε))-space Õ(√n log(W/ε))-pass streaming algorithm which during the last pass returns the flow on each edge up to an additive error of ε. The algorithm does not return the flow at the end of the last pass but returns the flow on an edge as the edge is read in the stream, circumventing existing Ω(n²) space lower bounds. In the 2-party communication model this implies Õ(n^{1.5} log² W) bits of communication.

What carries the argument

The on-the-fly reporting of approximate flow values during the final streaming pass, which avoids retaining the complete flow assignment in memory at any single time.

If this is right

  • The same approach yields Õ(n^{1.5} log² W) bits of communication in the two-party communication model.
  • Quadratic space lower bounds for storing every edge flow can be avoided when output is permitted incrementally during the last pass.
  • The technique extends to st-maximum flow and other flow problems that generalize minimum-cost flow.
  • Subquadratic space becomes feasible for computing and outputting flows rather than merely their sizes or costs.

Where Pith is reading between the lines

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

  • The on-the-fly output trick could apply to other graph problems where full solution vectors are required but can be emitted incrementally without full storage.
  • Similar space reductions may be possible in distributed or parallel models that share the streaming constraint on memory.
  • Testing the bounds on graphs with non-integer capacities would clarify how far the integer assumption is essential.
  • The communication-complexity consequence suggests possible improvements for multi-party settings where flow solutions must be exchanged.

Load-bearing premise

The graph is directed with integer capacities and costs bounded by W, and the algorithm is allowed to output the approximate flow value for each edge exactly when that edge appears in the final pass.

What would settle it

A directed graph with n vertices and integer capacities and costs at most W for which every streaming algorithm outputting all approximate edge flows on the fly requires more than Õ(n^{1.5} log(W/ε)) space or more than Õ(√n log(W/ε)) passes.

Figures

Figures reproduced from arXiv: 2605.09547 by Albert Weng, Jan van den Brand, Zhao Song.

Figure 1
Figure 1. Figure 1: Variable dependencies. E.g., querying x t e requires the value of τ t e . 4.2 Recap of IPM We start by reviewing the important definitions and lemmas that [BLL+21] uses in their interior point method. The barrier function [BLL+21] uses is given by ϕ(x) = − log(x−l)−log(u−x). Note ϕ ′ (x) = − 1 x−l + 1 u−x and ϕ ′′(x) = 1 (x−l) 2 − 1 (u−x) 2 . During the IPM, we maintain tuples (x, s, µ). Given a current po… view at source ↗
read the original abstract

Space complexity is a critical factor in various computational models, including streaming, parallel/distributed computing, and communication complexity. We study the space complexity of the minimum-cost flow problem, a generalization of the st-max flow problem, focusing on computing flows in subquadratic space. In the general case with arbitrary capacities, minimum cost and $st$-maximum flows can use up to $\Omega(n^2)$ edges, so computing the flow on each edge (rather than just the size/cost) seems impossible in subquadratic space. Indeed, there are lower bounds proving quadratic space is needed to store the flow on every edge, which has been used to prove lower bounds on streaming algorithms. However, we show that these lower bounds can be circumvented, opening up improvements for streaming and communication complexity. For a directed graph with integer capacities and costs bounded by $W$, we provide a $\tilde O(n^{1.5}\log (W/\epsilon))$-space $\tilde O(\sqrt{n} \log(W/\epsilon))$-pass streaming algorithm, which during the last pass returns the flow on each edge up to an additive error of $\epsilon$. Crucially, the algorithm does not return the flow at the end of the last pass but returns the flow on an edge, as the edge is read in the stream. This allows us to circumvent existing $\Omega(n^2)$ space lower bounds. In the 2-party communication model, our algorithm implies $\tilde O(n^{1.5}\log^2 W)$ bits of communication.

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

2 major / 2 minor

Summary. The manuscript presents a streaming algorithm for approximate minimum-cost flow on directed graphs with integer capacities and costs bounded by W. It achieves Õ(n^{1.5} log(W/ε)) space and Õ(√n log(W/ε)) passes, returning the flow value on each edge (additive error ε) on-the-fly during the final pass as the edge is read, rather than materializing the full flow vector. This output convention is claimed to circumvent Ω(n²) space lower bounds. The result also yields a 2-party communication protocol using Õ(n^{1.5} log² W) bits.

Significance. If verified, the result would be significant for streaming and communication complexity, as it shows subquadratic space is achievable for flow problems by relaxing the output model to on-the-fly reporting. This has the potential to weaken the impact of existing quadratic-space lower bounds and suggests new algorithmic approaches when the entire flow vector need not be stored simultaneously. The explicit dependence on n, W, and ε, together with the integer-capacity assumption, makes the claim concrete and potentially applicable.

major comments (2)
  1. [Abstract] Abstract: the central claim of an Õ(n^{1.5} log(W/ε))-space Õ(√n log(W/ε))-pass algorithm is stated without any construction, proof sketch, or high-level technique, making it impossible to verify the space/pass bounds or the approximation guarantee. This is load-bearing for the main result.
  2. [Abstract] The output model (reporting flow on an edge exactly when it appears in the final pass) is used to evade lower bounds, but no argument is given showing that the approximation and feasibility are preserved under this delayed, per-edge output; this is load-bearing because the lower-bound circumvention is the key novelty.
minor comments (2)
  1. The Õ notation hides polylog factors whose dependence on n, W, and ε should be made explicit in the full version.
  2. [Abstract] The communication-complexity implication is stated but the reduction from the streaming algorithm is not detailed.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive feedback on our manuscript. We address each major comment below and will revise the abstract and introduction for improved clarity while preserving the paper's technical content.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim of an Õ(n^{1.5} log(W/ε))-space Õ(√n log(W/ε))-pass algorithm is stated without any construction, proof sketch, or high-level technique, making it impossible to verify the space/pass bounds or the approximation guarantee. This is load-bearing for the main result.

    Authors: Abstracts are constrained by length and conventionally omit detailed proofs or sketches; the full manuscript contains the complete construction and analysis. The high-level technique is a combination of vertex sparsification to reduce the effective graph size to O(n^{1.5}) followed by a multi-phase streaming procedure that performs O(√n) passes to compute an approximate flow via successive cost scaling and residual graph updates. Space bounds arise from maintaining linear sketches of size O(n^{0.5} log(W/ε)) per vertex, and the approximation guarantee follows from a potential-function argument bounding the total additive error by ε per edge (Theorem 1, Sections 3–5). We will add a single high-level sentence to the abstract describing the sparsification-plus-iterative-scaling approach. revision: yes

  2. Referee: [Abstract] The output model (reporting flow on an edge exactly when it appears in the final pass) is used to evade lower bounds, but no argument is given showing that the approximation and feasibility are preserved under this delayed, per-edge output; this is load-bearing because the lower-bound circumvention is the key novelty.

    Authors: The preservation argument appears in the full paper: Section 2 formally defines the on-the-fly output model, and the proof of Theorem 1 (Section 5) shows that the algorithm maintains a globally feasible flow invariant across all passes. In the final pass, each edge's reported value is the exact final flow computed by the preceding phases; because the additive error is bounded uniformly and independently of storage (via the same potential function used for the approximation guarantee), feasibility and the ε-approximation are unaffected by the delayed reporting. The model evades Ω(n²)-space lower bounds precisely because the algorithm never materializes the entire flow vector at once. We will insert a concise paragraph in the introduction (and a parenthetical remark in the abstract) explicitly summarizing this invariant argument. revision: partial

Circularity Check

0 steps flagged

No significant circularity; explicit algorithmic construction

full rationale

The paper presents a direct streaming algorithm construction for approximate min-cost flow that achieves subquadratic space by using an on-the-fly output model during the final pass. This model is explicitly defined in the abstract and claim, allowing circumvention of known Ω(n²) lower bounds without any reduction to fitted parameters, self-definitional loops, or load-bearing self-citations. No equations or steps in the provided text equate a derived result to its inputs by construction; the bounds follow from the stated space/pass complexity and output convention. The derivation is self-contained as a constructive proof against standard streaming lower bounds.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard directed-graph and integer-capacity assumptions plus the streaming model definition; no free parameters or invented entities are introduced beyond the usual ε-approximation tolerance.

axioms (1)
  • domain assumption Input graph is directed with integer capacities and costs bounded by W
    Used to obtain the stated space and pass bounds in the streaming model.

pith-pipeline@v0.9.0 · 5574 in / 1229 out tokens · 57785 ms · 2026-05-12T01:51:44.806596+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.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [1]

    Polynomial pass lower bounds for graph stream- ing algorithms

    [ACK19] Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Polynomial pass lower bounds for graph stream- ing algorithms. In Moses Charikar and Edith Cohen, editors,Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 265–276. ACM,

    work page 2019

  2. [2]

    A simple semi-streaming algorithm for global minimum cuts

    [AD21] Sepehr Assadi and Aditi Dudeja. A simple semi-streaming algorithm for global minimum cuts. In Hung Viet Le and Valerie King, editors,4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pages 172–180. SIAM,

    work page 2021

  3. [3]

    Linear programming in the semi-streaming model with ap- plication to the maximum matching problem

    [AG11] Kook Jin Ahn and Sudipto Guha. Linear programming in the semi-streaming model with ap- plication to the maximum matching problem. In Luca Aceto, Monika Henzinger, and Jirí Sgall, editors,Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II, volume 6756 ofLecture N...

    work page 2011

  4. [4]

    Semi-streaming bipartite matching in fewer passes and optimal space

    [AJJ+22] Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Semi-streaming bipartite matching in fewer passes and optimal space. In Joseph (Seffi) Naor and Niv Buchbinder, editors,Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 627–6...

    work page 2022

  5. [5]

    On estimating maximum matching size in graph streams

    [AKL17] Sepehr Assadi, Sanjeev Khanna, and Yang Li. On estimating maximum matching size in graph streams. In Philip N. Klein, editor,Proceedings of the Twenty-Eighth Annual ACM-SIAM Sym- posium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1723–1742. SIAM,

    work page 2017

  6. [6]

    Distributed and streaming linear programming in low dimensions

    [AKZ19] Sepehr Assadi, Nikolai Karpov, and Qin Zhang. Distributed and streaming linear programming in low dimensions. In Dan Suciu, Sebastian Skritek, and Christoph Koch, editors,Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pages 236–253. ACM,

    work page 2019

  7. [7]

    Circulation control for faster minimum cost flow in unit-capacity graphs

    26 [AMV20] Kyriakos Axiotis, Aleksander Madry, and Adrian Vladu. Circulation control for faster minimum cost flow in unit-capacity graphs. InFOCS.https://arxiv.org/pdf/2003.04863,

    work page arXiv 2003

  8. [8]

    Hidden permutations to the rescue: Multi-pass streaming lower bounds for approximate matchings

    [AS23] Sepehr Assadi and Janani Sundaresan. Hidden permutations to the rescue: Multi-pass streaming lower bounds for approximate matchings. In64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 909–932. IEEE,

    work page 2023

  9. [9]

    A simple (1 -ϵ)-approximation semi-streaming algorithm for maximum (weighted) matching

    [Ass24] Sepehr Assadi. A simple (1 -ϵ)-approximation semi-streaming algorithm for maximum (weighted) matching. In Merav Parter and Seth Pettie, editors,2024 Symposium on Simplicity in Algorithms, SOSA 2024, Alexandria, VA, USA, January 8-10, 2024, pages 337–354. SIAM,

    work page 2024

  10. [10]

    Nearly optimal communication and query complexity of bipartite matching

    [BBE+22] Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai. Nearly optimal communication and query complexity of bipartite matching. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 1174–1185. IEEE,

    work page 2022

  11. [11]

    Complexity classes in communication complexity theory (preliminary version)

    [BFS86] László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory (preliminary version). In27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pages 337–347. IEEE Computer Society,

    work page 1986

  12. [12]

    Liu, Richard Peng, and Aaron Sidford

    [BGJ+22] Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, and Aaron Sidford. Faster maxflow via improved dynamic spectral vertex sparsifiers. In Stefano Leonardi and Anupam Gupta, editors,STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 543–556. ACM,

    work page 2022

  13. [13]

    Global vs

    [BJMY25] Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay, and Sorrachai Yingchareonthaworn- chai. Global vs. s-t vertex connectivity beyond sequential: Almost-perfect reductions and near- optimal separations. In Michal Koucký and Nikhil Bansal, editors,Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, Ju...

    work page 2025

  14. [14]

    Chan and Eric Y

    [CC05] Timothy M. Chan and Eric Y. Chen. Multi-pass geometric algorithms. In Joseph S. B. Mitchell and Günter Rote, editors,Proceedings of the 21st ACM Symposium on Computational Geometry, Pisa, Italy, June 6-8, 2005, pages 180–189. ACM,

    work page 2005

  15. [15]

    Vertex ordering problems in directed graph streams

    [CGMV20] Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, and Sofya Vorotnikova. Vertex ordering problems in directed graph streams. In Shuchi Chawla, editor,Proceedings of the 2020 ACM- SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1786–1802. SIAM,

    work page 2020

  16. [16]

    Saxena, Zhao Song, and Huacheng Yu

    27 [CKP+21] Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu. Almost optimal super-constant-pass streaming lower bounds for reachability. In Samir Khuller and Virginia Vassilevska Williams, editors,STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 570–...

    work page 2021

  17. [17]

    Cohen and Richard Peng

    [CP15] Michael B. Cohen and Richard Peng. L p row sampling by lewis weights. In Rocco A. Servedio and Ronitt Rubinfeld, editors,Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 183–192. ACM,

    work page 2015

  18. [18]

    Crouch and Daniel M

    [CS14] Michael S. Crouch and Daniel M. Stubbs. Improved streaming algorithms for weighted matching, via unweighted matching. In Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore, editors,Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain, ...

    work page 2014

  19. [19]

    Economic efficiency requires interaction

    [DNO14] Shahar Dobzinski, Noam Nisan, and Sigal Oren. Economic efficiency requires interaction. In David B. Shmoys, editor,Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 233–242. ACM,

    work page 2014

  20. [20]

    On the communication complexity of planarity

    [DP89] Pavol Duris and Pavel Pudlák. On the communication complexity of planarity. In János Csirik, János Demetrovics, and Ferenc Gécseg, editors,Fundamentals of Computation Theory, Inter- national Conference FCT’89, Szeged, Hungary, August 21-25, 1989, Proceedings, volume 380 of Lecture Notes in Computer Science, pages 145–147. Springer,

    work page 1989

  21. [21]

    Daitch and Daniel A

    [DS08a] Samuel I. Daitch and Daniel A. Spielman. Faster approximate lossy generalized flow via interior point algorithms. In Cynthia Dwork, editor,Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 451–460. ACM,

    work page 2008

  22. [22]

    Bipartite graph matchings in the semi- streaming model

    [EKS09] Sebastian Eggert, Lasse Kliemann, and Anand Srivastav. Bipartite graph matchings in the semi- streaming model. In Amos Fiat and Peter Sanders, editors,Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9,

    work page 2009

  23. [23]

    (∆+1) vertex coloring inO(n) communication

    [FM24] Maxime Flin and Parth Mittal. (∆+1) vertex coloring inO(n) communication. In Ran Gelles, Dennis Olivetti, and Petr Kuznetsov, editors,Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC 2024, Nantes, France, June 17-21, 2024, pages 416–424. ACM,

    work page 2024

  24. [24]

    A subquadratic two-party communication protocol for minimum cost flow.CoRR, abs/2510.03427,

    28 [GJ25] Hossein Gholizadeh and Yonggang Jiang. A subquadratic two-party communication protocol for minimum cost flow.CoRR, abs/2510.03427,

    work page arXiv

  25. [25]

    On the communication and stream- ing complexity of maximum bipartite matching

    [GKK12] Ashish Goel, Michael Kapralov, and Sanjeev Khanna. On the communication and stream- ing complexity of maximum bipartite matching. In Yuval Rabani, editor,Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 468–485. SIAM,

    work page 2012

  26. [26]

    Liu, and Richard Peng

    [GLP21] Yu Gao, Yang P. Liu, and Richard Peng. Fully dynamic electrical flows: Sparse maxflow faster than goldberg-rao. In62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 516–527. IEEE,

    work page 2021

  27. [27]

    Woodruff, and Guanghao Ye

    [GLP+24] Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan, William Swartworth, David P. Woodruff, and Guanghao Ye. Improving the bit complexity of communication for distributed convex opti- mization. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors,Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canad...

    work page 2024

  28. [28]

    On the communication complexity of graph properties

    [HMT88] András Hajnal, Wolfgang Maass, and György Turán. On the communication complexity of graph properties. In Janos Simon, editor,Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 186–191. ACM,

    work page 1988

  29. [29]

    New bounds on the classical and quantum communication complexity of some graph properties

    [IKL+12] Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, and Ronald de Wolf. New bounds on the classical and quantum communication complexity of some graph properties. In Deepak D’Souza, Telikepalli Kavitha, and Jaikumar Radhakrishnan, editors,IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 20...

    work page 2012

  30. [30]

    Minimums tcuts with fewer cut queries

    [JNS26] Yonggang Jiang, Danupon Nanongkai, and Pachara Sawettamalya. Minimums tcuts with fewer cut queries. In Kasper Green Larsen and Barna Saha, editors,Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 258–296. SIAM,

    work page 2026

  31. [31]

    Better bounds for matchings in the streaming model

    [Kap13] Michael Kapralov. Better bounds for matchings in the streaming model. In Sanjeev Khanna, ed- itor,Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1679–1697. SIAM,

    work page 2013

  32. [32]

    Maximum matching in semi-streaming with few passes

    [KMM12] Christian Konrad, Frédéric Magniez, and Claire Mathieu. Maximum matching in semi-streaming with few passes. In Anupam Gupta, Klaus Jansen, José D. P. Rolim, and Rocco A. Servedio, editors,Approximation, Randomization, and Combinatorial Optimization. Algorithms and Tech- niques - 15th International Workshop, APPROX 2012, and 16th International Work...

    work page 2012

  33. [33]

    Aframeworkforanalyzing resparsification algorithms

    [KPPS17] RasmusKyng, JakubPachocki, RichardPeng, andSushantSachdeva. Aframeworkforanalyzing resparsification algorithms. InSODA, pages 2032–2043. SIAM,

    work page 2032

  34. [34]

    Finding graph matchings in data streams

    [McG05] Andrew McGregor. Finding graph matchings in data streams. In Chandra Chekuri, Klaus Jansen, José D. P. Rolim, and Luca Trevisan, editors,Approximation, Randomization and Com- binatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approxima- tion Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th Inte...

    work page 2005

  35. [35]

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

    [MN20] Sagnik Mukhopadhyay and Danupon Nanongkai. Weighted min-cut: sequential, cut-query, and streaming algorithms. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors,Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 496–509. ACM,

    work page 2020

  36. [36]

    Mande, Manaswi Paraashar, Swagato Sanyal, and Nitin Saurabh

    [MPSS24] Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal, and Nitin Saurabh. On the communica- tion complexity of finding a king in a tournament. In Amit Kumar and Noga Ron-Zewi, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024, August 28-30, 2024, London School of Economics, London, U...

    work page 2024

  37. [37]

    Papadimitriou and Michael Sipser

    [PS82] Christos H. Papadimitriou and Michael Sipser. Communication complexity. In Harry R. Lewis, Barbara B. Simons, Walter A. Burkhard, and Lawrence H. Landweber, editors,Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA, pages 196–200. ACM,

    work page 1982

  38. [38]

    Matthew Weinberg

    [RSW18] 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, pages 39:1–39:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

    work page 2018

  39. [39]

    Vempala, Ruosong Wang, and David P

    [VWW20] Santosh S. Vempala, Ruosong Wang, and David P. Woodruff. The communication complexity of optimization. In Shuchi Chawla, editor,Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1733–

    work page 2020