  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(\log n)$ 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 $\tilde{O}(n)$ space, then a
near-optimal solution to the max cut value can be obtained by storing an
$\tilde{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 $\tilde{\Omega}(\sqrt{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
$\frac{1}{2}$-far from being bipartite, and establishing that
$\tilde{\Omega}(\sqrt{n})$ space is necessary to differentiate between these
two cases. Thus as a direct corollary we obtain that $\tilde{\Omega}(\sqrt{n})$
space is also necessary to test if a graph is bipartite or $\frac{1}{2}$-far
from being bipartite.
  We also show that for any $\epsilon > 0$, any streaming algorithm that
obtains a $(1 + \epsilon)$-approximation to the max cut value when edges arrive
in adversarial order requires $n^{1 - O(\epsilon)}$ space, implying that
$\Omega(n)$ space is necessary to obtain an arbitrarily good approximation to
the max cut value.
