2026-09-10T09:44:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27748 2026-09-09T12:19:36Z ddc:004 open_access

Unbounded-Width CSPs Are Untestable in a Sublinear Number of Queries Fei, Yumou constraint satisfaction problems property testing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yumou Fei 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.31 urn:nbn:de:0030-drops-277489 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.31 eng https://creativecommons.org/licenses/by/4.0/legalcode