ECCC-Report TR22-166https://eccc.weizmann.ac.il/report/2022/166Comments and Revisions published for TR22-166en-usWed, 23 Nov 2022 09:12:10 +0200
Paper TR22-166
| Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly |
Raghuvansh Saxena,
Gillat Kol,
Dmitry Paramonov,
Huacheng Yu
https://eccc.weizmann.ac.il/report/2022/166We study boolean constraint satisfaction problems (CSPs) $\mathrm{Max}\text{-}\mathrm{CSP}^f_n$ for all predicates $f: \{ 0, 1 \} ^k \to \{ 0, 1 \}$. In these problems, given an integer $v$ and a list of constraints over $n$ boolean variables, each obtained by applying $f$ to a sequence of literals, we wish to decide if there is an assignment to the variables that satisfies at least $v$ constraints. We consider these problems in the streaming model, where the algorithm makes a small number of passes over the list of constraints.
Our first and main result is the following complete characterization: For every predicate $f$, the streaming space complexity of the $\mathrm{Max}\text{-}\mathrm{CSP}^f_n$ problem is $\tilde{\Theta}(n^{\mathrm{deg}(f)})$, where $\mathrm{deg}(f)$ is the degree of $f$ when viewed as a multilinear polynomial. While the upper bound is obtained by a (very simple) one-pass streaming algorithm, our lower bound shows that a better space complexity is impossible even with constant-pass streaming algorithms.
Building on our techniques, we are also able to get an optimal $\Omega(n^2)$ lower bound on the space complexity of constant-pass streaming algorithms for the well studied $\mathrm{Max}\text{-}\mathrm{CUT}$ problem, even though it is not technically a $\mathrm{Max}\text{-}\mathrm{CSP}^f_n$ problem as, e.g., negations of variables and repeated constraints are not allowed.Wed, 23 Nov 2022 09:12:10 +0200https://eccc.weizmann.ac.il/report/2022/166