ECCC-Report TR22-161https://eccc.weizmann.ac.il/report/2022/161Comments and Revisions published for TR22-161en-usSun, 20 Nov 2022 07:39:49 +0200
Paper TR22-161
| Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut |
Raghuvansh Saxena,
Lijie Chen,
Gillat Kol,
Dmitry Paramonov,
Zhao Song,
Huacheng Yu
https://eccc.weizmann.ac.il/report/2022/161We 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.Sun, 20 Nov 2022 07:39:49 +0200https://eccc.weizmann.ac.il/report/2022/161