Streaming Lower Bounds for Approximating MAX-CUT

Michael Kapralov, Sanjeev Khanna, Madhu Sudan

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…