Open Problems:45 - Revision history

71.226.226.13: /* Updates */

2022-07-11T20:50:40Z

‎Updates

SVelusamy: /* Updates */

2022-06-27T05:12:48Z

‎Updates

SVelusamy: /* Updates */

2022-06-27T05:11:56Z

‎Updates

SVelusamy: /* Updates */

2022-06-27T04:55:35Z

‎Updates

SVelusamy: /* Updates */

2022-06-27T04:52:26Z

‎Updates

SVelusamy: /* Updates */

2022-06-27T03:59:07Z

‎Updates

SVelusamy: /* Updates */

2022-06-27T03:37:07Z

‎Updates

SVelusamy: /* Updates */

2022-06-27T03:32:03Z

‎Updates

Krzysztof Onak at 04:28, 28 April 2017

2017-04-28T04:28:38Z

Sassadi at 15:37, 20 April 2017

2017-04-20T15:37:49Z

← Older revision		Revision as of 20:50, 11 July 2022
Line 36:		Line 36:
	* 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 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}}.		* 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}}.

@@ Line 34: / Line 34: @@
 * 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-21a}}.
+* 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-21b}}.
+* 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}}.

← Older revision		Revision as of 05:11, 27 June 2022
Line 34:		Line 34:
	* 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 $(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}}.		* 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-21a}}.
		+	* 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-21b}}.

@@ Line 18: / Line 18: @@
 == Updates ==
 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}}.
-* In adversarial streams, $\Omega(n)$ space is needed to obtain a better than $1/2$ approximation {{cite|KapralovK-19}}.
+* $\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:
@@ Line 28: / Line 31: @@
 * 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$ approximation {{cite|ChouGV-20}}.
+* 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$ approximation for MAX-DICUT {{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}}.

@@ Line 25: / Line 25: @@
 The progress on general constraint satisfaction problems in the streaming setting:
-* For every $\varepsilon>0$, there is an $O(\log n)$ space $(4/9-\varepsilon)$-approximation 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-DICUT {{cite|GuruswamiVV-17}}.
-* For every $\varepsilon>0$, there is an $O(\log n)$ space $(4/9-\varepsilon)$-approximation sketching algorithm for MAX-2AND {{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
+* 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$ approximation {{cite|ChouGV-20}}.

← Older revision		Revision as of 03:59, 27 June 2022
Line 23:		Line 23:
	* In random-order streams, $\Omega(\sqrt{n})$ space is needed to obtain a better than $1/2$ approximation {{cite\|KapralovKS-15}}.		* In random-order streams, $\Omega(\sqrt{n})$ space is needed to obtain a better than $1/2$ approximation {{cite\|KapralovKS-15}}.
	* In adversarial streams, $\Omega(n)$ space is needed to obtain a better than $1/2$ approximation {{cite\|KapralovK-19}}.		* In adversarial streams, $\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 $(4/9-\varepsilon)$-approximation sketching algorithm for MAX-DICUT {{cite\|GuruswamiVV-17}}.
		+	* For every $\varepsilon>0$, there is an $O(\log n)$ space $(4/9-\varepsilon)$-approximation 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

@@ Line 17: / Line 17: @@
 '''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 ==
+== Updates ==
+The progress on the MAX-CUT problem in the streaming setting:
-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.
+* Estimating the maximum cut to within a factor of $(1-\varepsilon)$ requires $n^{1-O(\varepsilon)}$ space {{cite|KapralovKS-15|KoganK-15}}.

← Older revision		Revision as of 15:37, 20 April 2017
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.