Streaming lower bounds for approximating MAX-CUT

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 that uses only O (1ogn) space, namely, count the number of edges and output half of this value as the estimate for max cut value. On the other extreme, if one allows O (1og n) space, then a near-optimal solution to the max cut value can be obtained by storing an O (n)-size sparsifier that essentially preserves the max cut. An intriguing question is if poly-logarithmic space suffices to obtain a non-trivial approximation to the max-cut value (that is, beating the factor 2). It was recently shown that the problem of estimating the size of a maximum matching in a graph admits a non-trivial approximation in poly-logarithmic space. Our main result is that any streaming algorithm that breaks the 2-approximation barrier requires ω (√n) space even if the edges of the input graph are presented in random order. Our result is obtained by exhibiting a distribution over graphs which are either bipartite or 1/2-far from being bipartite, and establishing that ω (√n) space is necessary to differentiate between these two cases. Thus as a direct corollary we obtain that ω (√n) space is also necessary to test if a graph is bipartite or a-far from being bipartite. We also show that for any ∈ > 0, any streaming algorithm that obtains a (1 + ∈)-approximation to the max cut value when edges arrive in adversarial order requires n1-O (∈) space, implying that ω (√n) space is necessary to obtain an arbitrarily good approximation to the max cut value.