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,ldots,q-1, we prove that improving over the trivial approximability by a factor of q requires Omega(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 Omega(n) space. The key technical core is an optimal, q-(k-1)-inapproximability for the Max k-LIN-bmod; q problem, which is the Max CSP problem where every constraint is given by a system of k-1 linear equations bmod; 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 MaxCut problem in graphs. MaxCut corresponds roughly to the case of Max k-LIN-bmod; q with k=q=2. For general CSPs in the streaming setting, prior results only yielded Omega(√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-bmod; 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.