An Optimal Space Lower Bound for Approximating MAX-CUT

Michael Kapralov, Dmitry Krachun

We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. At one extreme, there is a trivial $2$-approximation for this problem t…