  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 the
size of the MAX-CUT. On the other extreme, for any fixed $\epsilon > 0$, if one
allows $\tilde{O}(n)$ space, a $(1+\epsilon)$-approximate solution to the
MAX-CUT value can be obtained by storing an $\tilde{O}(n)$-size sparsifier that
essentially preserves MAX-CUT value.
  Our main result is that any (randomized) single pass streaming algorithm that
breaks the $2$-approximation barrier requires $\Omega(n)$-space, thus resolving
the space complexity of any non-trivial approximations of the MAX-CUT value to
within polylogarithmic factors in the single pass streaming model. We achieve
the result by presenting a tight analysis of the Implicit Hidden Partition
Problem introduced by Kapralov et al.[SODA'17] for an arbitrarily large number
of players. In this problem a number of players receive random matchings of
$\Omega(n)$ size together with random bits on the edges, and their task is to
determine whether the bits correspond to parities of some hidden bipartition,
or are just uniformly random.
  Unlike all previous Fourier analytic communication lower bounds, our analysis
does not directly use bounds on the $\ell_2$ norm of Fourier coefficients of a
typical message at any given weight level that follow from hypercontractivity.
Instead, we use the fact that graphs received by players are sparse (matchings)
to obtain strong upper bounds on the $\ell_1$ norm of the Fourier coefficients
of the messages of individual players, and then argue, using the convolution
theorem, that similar strong bounds on the $\ell_1$ norm are essentially
preserved once messages of different players are combined.

Data Structures and Algorithms