Linear space streaming lower bounds for approximating CSPs

We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on n variables taking values in 0, . . . , q -1, we prove that improving over the trivial approximability by a factor of q requires Ω(n) space even on instances with O(n) constraints. We also identify a broad subclass of problems for which any improvement over the trivial approximability requires Ω(n) space. The key technical core is an optimal, q -(k-1) -inapproximability for the Max k-LIN-mod q problem, which is the Max CSP problem where every constraint is given by a system of k -1 linear equations mod q over k variables.

Our work builds on and extends the breakthrough work of Kapralov and Krachun (Proc. STOC 2019) who showed a linear lower bound on any non-trivial approximation of the Max-Cut problem in graphs. MaxCut corresponds roughly to the case of Max k-LIN-mod q with k = q = 2. For general CSPs in the streaming setting, prior results only yielded Ω( √ n) space bounds. In particular no linear space lower bound was known for an approximation factor less than 1/2 for any CSP. Extending the work of Kapralov and Krachun to Max k-LIN-mod q to k > 2 and q > 2 (while getting optimal hardness results) is the main technical contribution of this work. Each one of these extensions provides non-trivial technical challenges that we overcome in this work.