Editing Open Problems:45

{{Header
|title=Streaming Max-Cut/Max-CSP
|source=bertinoro11
|who=Robert Krauthgamer
}}
The problem is defined as follows: given a stream of edges of an $n$-node graph $G$, estimate the value of the maximum cut in $G$.

'''Question:''' Is there an algorithm with an approximation factor strictly better than $1/2$ that uses $o(n)$  space? 

'''Background:''' Note that $1/2$ is achievable using random assignment
argument. Moreover, using sparsification arguments {{cite|Trevisan-09|AhnG-09}}, one can
obtain a better approximation ratio using $O(n \operatorname{polylog} n)$ space.
Woodruff and Bhattacharyya (private communication) noted that
subsampling $O(n/\epsilon^2)$ edges gives,  with high probability, an
$\epsilon$-additive approximation for all cuts, and thus
$1+\epsilon$ multiplicative approximation for MAX-CUT.

'''Question:''' What about general constraint satisfaction problems with fixed clause-length and alphabet-size? In this case it is even not known how to obtain $O(n \operatorname{polylog} n)$ space bound.