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

The bounded-degree query model, introduced by Goldreich and Ron ($\mathit{\text{Algorithmica,}}\mathit{\text{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 $\mathrm{\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{N}\mathbf{P}$-hard to solve, including $k$-colorability of $\mathrm{\ell }$-uniform hypergraphs for any $k,\mathrm{\ell }\ge 2$ with $(k,\mathrm{\ell })\mathrm{\ne }(2,2)$. Our proof combines the techniques from Bogdanov, Obata, and Trevisan ($\mathit{\text{FOCS,}}\mathit{\text{2002}}$), who established the first $\mathrm{\Omega }(n)$ query lower bound for CSP testing in the bounded-degree model, with known results from universal algebra.