In the Max-Cut problem in the streaming model, an algorithm is given the edges of an unknown graph $G = (V,E)$ in some fixed order, and its goal is to approximate the size of the largest cut in $G$. Improving upon an earlier result of Kapralov, Khanna and Sudan, it was shown by Kapralov and Krachun that for all $\eps>0$, no $o(n)$ memory streaming algorithm can achieve a $(1/2+\eps)$-approximation for Max-Cut. Their result holds for single-pass streams, i.e. the setting in which the algorithm only views the stream once, and it was open whether multi-pass access may help. The state-of-the-art result along these lines, due to Assadi and N, rules out arbitrarily good approximation algorithms with constantly many passes and $n^{1-\delta}$ space for any $\delta>0$.

 

In this talk, I will talk about our new result in this direction, showing that $1/2$ is the best approximation ratio even in the multi-pass setting. More specifically, we show that for all $\eps>0$, a $k$-pass streaming $(1/2+\eps)$-approximation algorithm for Max-Cut requires $\Omega_{\eps}\left(n^{1/3}/k\right)$ space. This result leads to a similar lower bound for the Maximum Directed Cut problem, showing the near optimality of the algorithm of Saxena, Singer,  Sudan, and Velusamy. Our proof uses a recent advance in analysis of Boolean functions—global hypercontractivity—together with a regularity decomposition technique inspired by query-to-communication lifting theorems, which may be of independent interests.

Shuo Wang is a second-year PhD student in Mathematics at MIT, advised by Dor Minzer. His research focuses on communication complexity and analysis of Boolean functions. Previously, he received his bachelor's degree from ACM Class at Shanghai Jiao Tong University.