Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914159717777408 |
|---|---|
| author | Fei, Yumou |
| author_facet | Fei, Yumou |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_27012 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Unbounded-width CSPs are Untestable in a Sublinear Number of Queries Fei, Yumou Computational Complexity Data Structures and Algorithms 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. |
| title | Unbounded-width CSPs are Untestable in a Sublinear Number of Queries |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.27012 |