We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. We show that there exists a constant $\\e_* > 0$ such that any randomized streaming algorithm that computes a $(1+\\e_*)$-approximation to MAX-CUT requires $\\Omega(n)$ space on an $n$ vertex graph. By contrast, there are algorithms that produce a $(1+\\e)$-approximation in space $O(n\/\\e^2)$ for every $\\e > 0$. Our result is the first linear space lower bound for the task of approximating the max cut value and partially answers an open question from the\u00a0literature~\\cite{Ber67}. The prior state of the art ruled out\u00a0$(2-\\epsilon)$-approximation in $\\tilde{O}(\\sqrt{n})$ space or $(1+\\e)$-approximation in $n^{1-O(\\e)}$ space, for any $\\epsilon > 0$.<\/p>\n
Previous lower bounds for the MAX-CUT problem relied, in essence, on a lower bound on the communication complexity of the following task: Several players are each given\u00a0some edges of a graph and they wish to determine if the union of these edges is $\\e$-close to forming a bipartite graph, using one-way communication. The previous works proved a lower bound of $\\Omega(\\sqrt{n})$ for this task when $\\e=1\/2$, and\u00a0$n^{1-O(\\e)}$ for every $\\e>0$, even when one of the players is given a candidate bipartition of the promised to be bipartite with respect to this partition or $\\e$-far from bipartite. This added information was essential in enabling the previous analyses but also yields a weak bound since, with this extra information, there is an $n^{1-O(\\e)}$ communication protocol for this problem. In this work, we give an $\\Omega(n)$ lower bound on the communication complexity of the original problem (without the extra\u00a0information) for $\\e=\\Omega(1)$ in the three-player setting. Obtaining this\u00a0$\\Omega(n)$ lower bound on the communication complexity is the main technical\u00a0result in this paper. We achieve it by a delicate choice of distributions on instances as well as a novel use of the convolution theorem from Fourier analysis combined with graph-theoretic considerations to analyze the communication complexity.<\/p>\n