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