In the standard framework of graph property testing and sublinear-time algorithms, the bounded-degree query model introduced by Goldreich and Ron in 2002 is a significant area of study. Many properties investigated 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 $\textbf{unbounded-width}$ CSPs, testing satisfiability requires $\Omega(n)$ queries in the bounded-degree model. This result unifies and generalizes several previous lower bounds, particularly applying to all CSPs known to be $\text{NP}$-hard, including $k$-colorability of $l$-uniform hypergraphs for any $k,l \geq 2$ with $(k,l) \neq (2,2)$.
Our proof combines techniques from Bogdanov, Obata, and Trevisan, who established the first $\Omega(n)$ query lower bound for CSP testing in the bounded-degree model, with known results from universal algebra.
Blogger's Review: This study provides a crucial theoretical foundation for understanding the complexity of unbounded-width CSPs, highlighting the challenges of testing satisfiability in sublinear queries, which is significant for researchers in graph theory and computational complexity. By integrating existing lower bound results, this paper points the way for future research.