Linear Space Streaming Lower Bounds for Approximating CSPs

View PDF HTML (experimental)

Abstract: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(\sqrt{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.

Comments: Revised SICOMP version

Subjects:

Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)

Cite as: arXiv:2106.13078 [cs.CC]

(or arXiv:2106.13078v4 [cs.CC] for this version)

https://doi.org/10.48550/arXiv.2106.13078

arXiv-issued DOI via DataCite

Submission history

From: Santhoshini Velusamy [view email] [v1] Thu, 24 Jun 2021 15:04:07 UTC (420 KB) [v2] Sun, 24 Apr 2022 20:31:37 UTC (655 KB) [v3] Fri, 7 Mar 2025 20:13:49 UTC (1,071 KB) [v4] Thu, 2 Apr 2026 15:55:24 UTC (1,089 KB)