Unbounded-Width CSPs Are Untestable in a Sublinear Number of Queries

The bounded-degree query model, introduced by Goldreich and Ron (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 unbounded-width CSPs, testing satisfiability requires Ω(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 NP-hard to solve, including k-colorability of 𝓁-uniform hypergraphs for any k,𝓁 ⩾ 2 with (k,𝓁) ≠ (2,2). Our proof combines the techniques from Bogdanov, Obata, and Trevisan (FOCS, 2002), who established the first Ω(n) query lower bound for CSP testing in the bounded-degree model, with known results from universal algebra.