Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-161 | 9th November 2022 23:43

Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut


Authors: Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
Publication: 20th November 2022 07:39
Downloads: 534


We consider the Max-Cut problem, asking how much space is needed by a streaming algorithm in order to estimate the value of the maximum cut in a graph. This problem has been extensively studied over the last decade, and we now have a near-optimal lower bound for one-pass streaming algorithms, showing that they require linear space to guarantee a better-than-$2$ approximation [KKS15, KK19]. The result relies on a lower bound for the cycle-finding problem, showing that it is hard for a one-pass streaming algorithm to find a cycle in a union of matchings.

The end-goal of our research is to prove a similar lower for multi-pass streaming algorithms that guarantee a better-than-$2$ approximation for Max-Cut, a highly challenging open problem. In this paper, we take a significant step in this direction, showing that even $o(\log n)$-pass streaming algorithms need $n^{\Omega(1)}$ space to solve the cycle-finding problem. Our proof is quite involved, dividing the cycles in the graph into "short" and "long" cycles, and using tailor-made lower bound techniques to handle each case.

ISSN 1433-8092 | Imprint