| Latest revision |
Your text |
| Line 18: |
Line 18: |
| | | | |
| | == Updates == | | == Updates == |
| − |
| |
| − | (''Unless explicitly mentioned, the stream is adversarial'')
| |
| − |
| |
| | The progress on the MAX-CUT problem in the streaming setting: | | 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}}. | | * 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}}. | | * 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 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}}. | + | * 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 $(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}}.
| |
