{"ID":2848269,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.27012","arxiv_id":"2510.27012","title":"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 $Ω(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) \\neq (2,2)$. Our proof combines the techniques from Bogdanov, Obata, and Trevisan (\\textit{FOCS, 2002}), who established the first $Ω(n)$ query lower bound for CSP testing in the bounded-degree model, with known results from universal algebra.","short_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 sati...","url_abs":"https://arxiv.org/abs/2510.27012","url_pdf":"https://arxiv.org/pdf/2510.27012v2","authors":"[\"Yumou Fei\"]","published":"2025-10-30T21:24:51Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[\"LoRA\"]","has_code":false}