Linear Space Streaming Lower Bounds for Approximating CSPs
share
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 case where every constraint is given by a system of k-1 linear equations q over k variables. Prior to our work, no such hardness was known for an approximation factor less than 1/2 for 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 the max cut in graphs. This corresponds roughly to the case of Max k-LIN-q with k=q=2. Each one of the extensions provides non-trivial technical challenges that we overcome in this work.
READ FULL TEXT