Difference between revisions of "Open Problems:45"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Created page with "{{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$, e...")
 
(Updates)
 
(10 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Streaming Max-Cut/Max-CSP
 
 
|source=bertinoro11
 
|source=bertinoro11
 
|who=Robert Krauthgamer
 
|who=Robert Krauthgamer
Line 17: 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.
 +
 +
== Updates ==
 +
 +
(''Unless explicitly mentioned, the stream is adversarial'')
 +
 +
The progress on the MAX-CUT problem in the streaming setting:
 +
* Estimating the maximum cut to within a factor of $(1-\varepsilon)$ requires $n^{1-O(\varepsilon)}$ space {{cite|KapralovKS-15|KoganK-15}}.
 +
* There exists a constant $\varepsilon_*>0$ such that obtaining a $(1-\varepsilon_*)$ approximation to MAX-CUT requires $\Omega(n)$ space {{cite|KapralovKSV-17}}.
 +
* In random-order streams, $\Omega(\sqrt{n})$ space is needed to obtain a better than $1/2$ approximation {{cite|KapralovKS-15}}.
 +
* $\Omega(n)$ space is needed to obtain a better than $1/2$ approximation {{cite|KapralovK-19}}.
 +
 +
The progress on general constraint satisfaction problems in the streaming setting:
 +
* For every $\varepsilon>0$, there is an $O(\log n)$ space $(2/5-\varepsilon)$-approximation linear sketching algorithm for MAX-DICUT {{cite|GuruswamiVV-17}}.
 +
* For every $\varepsilon>0$, there is an $O(\log n)$ space $(2/5-\varepsilon)$-approximation linear sketching algorithm for MAX-2AND {{cite|GuruswamiVV-17}}.
 +
* $\Omega(\sqrt{n})$ space is needed to obtain a better than $1/2$ approximation for MAX-DICUT (also MAX-2AND) {{cite|GuruswamiVV-17}}.
 +
* Dichotomy theorem for streaming approximation of all Boolean Max-2CSPs: For every Boolean Max-2CSP, there is an explicit constant $\alpha$ such that for every $\varepsilon$, (i) there is an $O(\log n)$ space $(\alpha-\varepsilon)$-approximation linear sketching algorithm and (ii) $\Omega(\sqrt{n})$ space is needed to obtain a better than $\alpha$ streaming approximation {{cite|ChouGV-20}}.
 +
* For every $\varepsilon>0$, there is an $O(\log n)$ space $(4/9-\varepsilon)$-approximation linear sketching algorithm for MAX-DICUT; $\Omega(\sqrt{n})$ space is needed to obtain a better than $4/9$ streaming approximation {{cite|ChouGV-20}}.
 +
* For every $\varepsilon>0$, there is an $O(\log n)$ space $(1/\sqrt{2}-\varepsilon)$-approximation linear sketching algorithm for MAX-$k$SAT; $\Omega(\sqrt{n})$ space is needed to obtain a better than $1/\sqrt{2}$ streaming approximation {{cite|ChouGV-20}}.
 +
* Dichotomy theorem for sketching approximation of all Boolean Max-CSPs: For every Boolean Max-CSP, there is a constant $\alpha$ such that for every $\varepsilon$, (i) there is an $O(\log n)$ space $(\alpha-\varepsilon)$-approximation linear sketching algorithm and (ii) $\Omega(\sqrt{n})$ space is needed to obtain a better than $\alpha$ sketching approximation {{cite|ChouGSV-21}}.
 +
* Dichotomy theorem for sketching approximation of all finite Max-CSPs: For every finite Max-CSP, there is a constant $\alpha$ such that for every $\varepsilon$, (i) there is an $O(\log n)$ space $(\alpha-\varepsilon)$-approximation linear sketching algorithm and (ii) $\Omega(\sqrt{n})$ space is needed to obtain a better than $\alpha$ sketching approximation {{cite|ChouGSV-21a}}.
 +
 +
See Madhu Sudan's latest survey on streaming and sketching complexity of CSPs {{cite|Sudan-22}}.

Latest revision as of 20:50, 11 July 2022

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.

Updates[edit]

(Unless explicitly mentioned, the stream is adversarial)

The progress on the MAX-CUT problem in the streaming setting:

  • Estimating the maximum cut to within a factor of $(1-\varepsilon)$ requires $n^{1-O(\varepsilon)}$ space [KapralovKS-15,KoganK-15].
  • There exists a constant $\varepsilon_*>0$ such that obtaining a $(1-\varepsilon_*)$ approximation to MAX-CUT requires $\Omega(n)$ space [KapralovKSV-17].
  • In random-order streams, $\Omega(\sqrt{n})$ space is needed to obtain a better than $1/2$ approximation [KapralovKS-15].
  • $\Omega(n)$ space is needed to obtain a better than $1/2$ approximation [KapralovK-19].

The progress on general constraint satisfaction problems in the streaming setting:

  • For every $\varepsilon>0$, there is an $O(\log n)$ space $(2/5-\varepsilon)$-approximation linear sketching algorithm for MAX-DICUT [GuruswamiVV-17].
  • For every $\varepsilon>0$, there is an $O(\log n)$ space $(2/5-\varepsilon)$-approximation linear sketching algorithm for MAX-2AND [GuruswamiVV-17].
  • $\Omega(\sqrt{n})$ space is needed to obtain a better than $1/2$ approximation for MAX-DICUT (also MAX-2AND) [GuruswamiVV-17].
  • Dichotomy theorem for streaming approximation of all Boolean Max-2CSPs: For every Boolean Max-2CSP, there is an explicit constant $\alpha$ such that for every $\varepsilon$, (i) there is an $O(\log n)$ space $(\alpha-\varepsilon)$-approximation linear sketching algorithm and (ii) $\Omega(\sqrt{n})$ space is needed to obtain a better than $\alpha$ streaming approximation [ChouGV-20].
  • For every $\varepsilon>0$, there is an $O(\log n)$ space $(4/9-\varepsilon)$-approximation linear sketching algorithm for MAX-DICUT; $\Omega(\sqrt{n})$ space is needed to obtain a better than $4/9$ streaming approximation [ChouGV-20].
  • For every $\varepsilon>0$, there is an $O(\log n)$ space $(1/\sqrt{2}-\varepsilon)$-approximation linear sketching algorithm for MAX-$k$SAT; $\Omega(\sqrt{n})$ space is needed to obtain a better than $1/\sqrt{2}$ streaming approximation [ChouGV-20].
  • Dichotomy theorem for sketching approximation of all Boolean Max-CSPs: For every Boolean Max-CSP, there is a constant $\alpha$ such that for every $\varepsilon$, (i) there is an $O(\log n)$ space $(\alpha-\varepsilon)$-approximation linear sketching algorithm and (ii) $\Omega(\sqrt{n})$ space is needed to obtain a better than $\alpha$ sketching approximation [ChouGSV-21].
  • Dichotomy theorem for sketching approximation of all finite Max-CSPs: For every finite Max-CSP, there is a constant $\alpha$ such that for every $\varepsilon$, (i) there is an $O(\log n)$ space $(\alpha-\varepsilon)$-approximation linear sketching algorithm and (ii) $\Omega(\sqrt{n})$ space is needed to obtain a better than $\alpha$ sketching approximation [ChouGSV-21a].

See Madhu Sudan's latest survey on streaming and sketching complexity of CSPs [Sudan-22].