Linear Space Lower Bounds for Approximating q-ary CSPs in the Streaming Model

Chi-Ning Chou
Alexander Golovnev
Madhu Sudan
Santhoshini Velusamy
STOC 2022(2022)
Google Scholar


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 case where every constraint is given by a system of $k-1$ linear equations $\bmod\; q$ over $k$ variables. Prior to our work, no such hardness was known for an approximation factor less than $1/2$ for {\em any} CSP. Our work builds on and extends the work of Kapralov and Krachun (Proc. STOC 2019) who showed a~linear lower bound on any non-trivial approximation of MAX CUTs in graphs. This corresponds roughly to the case of MAX $k$-LIN-$\bmod\; q$ with $k=q=2$. Each one of the extensions provides non-trivial technical challenges that we overcome in this work.