Unbounded-width CSPs are Untestable in a Sublinear Number of Queries

Abstract

The bounded-degree query model, introduced by Goldreich and Ron (\textit{Algorithmica, 2002}), is a standard framework in graph property testing and sublinear-time algorithms. Many properties studied in this model, such as bipartiteness and 3-colorability of graphs, can be expressed as satisfiability of constraint satisfaction problems (CSPs). We prove that for the entire class of \emph{unbounded-width} CSPs, testing satisfiability requires $\Omega (n)$ queries in the bounded-degree model. This result unifies and generalizes several previous lower bounds. In particular, it applies to all CSPs that are known to be $\mathbf{NP}$-hard to solve, including $k$-colorability of $\ell$-uniform hypergraphs for any $k,\ell \ge 2$ with $(k,\ell )\ne (2,2)$. Our proof combines the techniques from Bogdanov, Obata, and Trevisan (\textit{FOCS, 2002}), who established the first $\Omega (n)$ query lower bound for CSP testing in the bounded-degree model, with known results from universal algebra.

arXiv commentadded in the second version: handling repetition of variables in constraints added in the third version: various typos corrected