# Difference between revisions of "Open Problems:45"

m (updated header) |
|||

Line 16: | Line 16: | ||

'''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. | '''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. | ||

+ | |||

+ | == Update == | ||

+ | |||

+ | It was shown in {{cite|KapralovKS-15|KoganK-15}} that estimating the maximum cut to within a factor of $(1-\varepsilon)$ requires $n^{1-O(\varepsilon)}$ space in graph streams. This was further improved in {{cite|KapralovKSV-17}} who showed that there exists some fixed constant $\varepsilon_*$ for which obtaining a $(1-\varepsilon_*)$ approximation to MAX-CUT requires $\Omega(n)$ space. Moreover, {{cite|KapralovKS-15}} proved that even in random-ordered streams, $\Omega(\sqrt{n})$ space is needed to obtain a better than $1/2$ approximation. |

## Revision as of 15:37, 20 April 2017

Suggested by | Robert Krauthgamer |
---|---|

Source | Bertinoro 2011 |

Short link | https://sublinear.info/45 |

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 [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.

## Update

It was shown in [KapralovKS-15,KoganK-15] that estimating the maximum cut to within a factor of $(1-\varepsilon)$ requires $n^{1-O(\varepsilon)}$ space in graph streams. This was further improved in [KapralovKSV-17] who showed that there exists some fixed constant $\varepsilon_*$ for which obtaining a $(1-\varepsilon_*)$ approximation to MAX-CUT requires $\Omega(n)$ space. Moreover, [KapralovKS-15] proved that even in random-ordered streams, $\Omega(\sqrt{n})$ space is needed to obtain a better than $1/2$ approximation.