Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
Yumou Fei, Dor Minzer, Shuo Wang · 2025
Read Multi-Pass Streaming Lower Bounds for Approximating Max-Cut by Yumou Fei, Dor Minzer, Shuo Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-23404.txt.
Description
Yumou Fei, Dor Minzer, and Shuo Wang prove a limit on streaming algorithms in a 2025 paper. In the streaming setting, a graph's edges arrive one by one and memory is scarce. The question is how well a program can estimate the largest cut, the best split of the graph's nodes into two groups, without storing the whole graph.
Earlier results blocked good approximations for programs that see the stream once, and for programs with a few passes and large memory. The new bound says any useful approximation needs either very many passes or serious memory: roughly, memory must shrink no faster than the cube root of the graph size divided by passes. The proof runs through a communication problem the authors lower-bound first. A matching result for directed cuts shows a known algorithm is nearly the best possible.
Catalog record
| CREATOR | Yumou Fei, Dor Minzer, Shuo Wang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 136 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-23404