Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
Yumou Fei · 2025
Read Unbounded-width CSPs are Untestable in a Sublinear Number of Queries by Yumou Fei (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-27012.txt.
Introduction
Yumou Fei proves a broad limit on fast property testing for constraint problems. In the bounded-degree query model, a tester probes only a small part of a huge graph to judge a property. Many properties, such as bipartiteness and colorability, can be written as constraint satisfaction problems, where values must meet a set of rules.
Fei shows that for every unbounded-width problem in this class, testing satisfiability needs a number of queries that grows with the whole input size. No sublinear shortcut exists for the full class. The result unifies several older lower bounds and covers all such problems known to be hard to solve exactly, including hypergraph coloring cases. The proof merges earlier testing techniques with results from universal algebra.
Catalog record
| CREATOR | Yumou Fei |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 103 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-27012
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Unbounded-width CSPs are Untestable in a Sublinear Number of Queries Yumou Fei Abstract 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 ) \Omega(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 k -colorability of ℓ \ell -uniform hypergraphs for any k , ℓ ⩾ 2 k,\ell\geqslant 2 with ( k , ℓ ) ≠ ( 2 , 2 ) (k,\ell)\neq(2,2) . Our proof combines the techniques from Bogdanov, Obata, and Trevisan ( FOCS, 2002 ), who established the first Ω ( n ) \Omega(n) query lower bound for CSP testing in the bounded-degree model, with known results from universal algebra. 1 Introduction Property testing is a class of algorithmic problems in which the algorithm is allowed to inspect only a small portion of the input. In exchange for this limited access, the goal is relaxed: instead of deciding whether the input exactly satisfies a given property, the tester must merely distinguish inputs that satisfy the property from those that are far from satisfying it, under an appropriate notion of distance. In this paper, we consider the problem of testing satisfiability of constraint satisfaction problems (CSPs). We formally define CSPs as follows. First of all, every CSP considered in this paper is specified by a finite template . Definition 1.1 . A relational structure is a pair (D,\Gamma) where D is a finite set, and \Gamma is a finite collection of relations on D . Each relation R\in\Gamma is a function R:D^{k}\to\{0,1\} for some positive integer k (called the arity of R ). A fixed relational structure (D,\Gamma) is also referred to as a CSP template . As a running example, if we let D=\{0,1\} and take \Gamma=\{\mathds{1}_{\{10,01\}}\} , where \mathds{1}_{\{10,01\}}(x,y)=1 if and only if x\neq y , then the template (D,\Gamma) could express the bipartiteness property of graphs, as we will soon explain. Given a CSP template (D,\Gamma) , we can collect all instances of the CSP into an infinite set \mathrm{CSP}(\Gamma) . Definition 1.2 . Given a CSP template (D,\Gamma) , we define \mathrm{CSP}(\Gamma) as the (infinite) collection of all instances I=(V,\mathcal{C}) , where V is a finite set of variables and \mathcal{C}=\{C_{1},\dots,C_{m}\} is a multi-set of constraints satisfying the following. Each constraint C_{i} is a pair (\mathbf{v},R) , where \mathbf{v}=(v_{1},\dots,v_{k}) is a tuple of distinct 1 1 1 Some authors allow repetition of variables in a constraint. In our setting, one can also “artificially” allow repetitions by adding more relations to the relational structure. variables from V , and R:D^{k}\to\{0,1\} is a relation from \Gamma . The variable set \{v_{1},\dots,v_{k}\}\subseteq V is called the scope of C_{i} . Now an instance in \mathrm{CSP}(\{\mathds{1}_{\{10,01\}}\}) can be viewed as a graph, with variables as vertices and constraints as edges. The graph is bipartite if and only if the CSP instance is “satisfiable,” as defined in the following definition. Definition 1.3 . An assignment for an instance I=(V,\mathcal{C})\in\mathrm{CSP}(\Gamma) is a map \tau:V\rightarrow D . We say \tau satisfies a constraint ((v_{1},\dots,v_{k}),R) if R\big(\tau(v_{1}),\dots,\tau(v_{k})\big)=1 . The value of an assignment \tau , denoted by \mathrm{val}_{I}(\tau) , is the fraction of constraints in \mathcal{C} satisfied by \tau . Note that \mathrm{val}_{I}(\tau)\in[0,1] . If \mathrm{val}_{I}(\tau)=1 , we say that \tau satisfies the instance I , or \tau is a satisfying assignment of I . The value of the instance I , denoted by \mathrm{val}_{I} , is the maximum possible value any assignment may achieve. The CSP defined by the bipartiteness template \big(\{0,1\},\{\mathds{1}_{\{10,01\}}\}\big) will be denoted by \mathsf{2COL} . Similarly, the property of vertex 3-colorability in graphs can be expressed by as a constraint satisfaction problem denoted by \mathsf{3COL} . 1.1 Testing CSP Satisfiability We study the property testing of CSP satisfiability in the bounded-degree query model , defined in Definition 1.5 below. In this model, the input CSP instance has a fixed variable set, and the degree of each variable (i.e. the number of contraints involving the variable) in the instance is assumed to be uniformly bounded by a constant. Definition 1.4 . Let (D,\Gamma) be a CSP template and let V be a set of variables. We write \mathrm{CSP}(\Gamma,V)\subseteq\mathrm{CSP}(\Gamma) for the collection of all \mathrm{CSP}(\Gamma) -instances whose variable set is V . Definition 1.5 . Fix a CSP template (D,\Gamma) . In the \mathrm{BD}(d,n) model for testing satisfiability, the tester is given oracle access to a CSP instance I=([n],\mathcal{C})\in\mathrm{CSP}(\Gamma,[n]) with maximum degree at most d . The goal of an \varepsilon -tester, where \varepsilon>0 is a fixed constant, is to achieve the following: (1) If I is satisfiable, the tester must accept I with probability at least 2/3 . (2) If at least \varepsilon dn constraints must be removed from \mathcal{C} to make I satisfiable, the tester must reject I with probability at least 2/3 . The tester accesses the instance I through oracle queries : when the tester queries a variable v\in[n] , the oracle reveals an arbitrary one of the previously unseen constraints involving v , unless all constraints involving v have been revealed (in which case the oracle returns \perp ). The bounded-degree query model was first introduced by [ GR02 ] , in the context of graph property testing. One of the earliest results in this model is that testing bipartiteness (i.e. testing satisfiability of \mathsf{2COL} instances) requires at least \Omega(\sqrt{n}) queries [ GR02 ] (for some degree bound d and error \varepsilon>0 ) and can be done with at most \widetilde{O}(\sqrt{n}) queries [ GR99 ] (for any degree bound d and any error \varepsilon>0 ). In contrast, Bogdanov, Obata, and Trevisan [ BOT02 ] showed that testing vertex 3-colorability requires \Omega(n) queries. 2 2 2 These seminal works, along with a large number of subsequent studies (such as [ GR11 , BSS10 , YI10 , YI12 , CMOS19 ] , to name a few), also investigated a wide range of other graph properties within the bounded-degree model, many of which are not constraint satisfaction problems. The study of testing CSP satisfiability in the bounded-degree model was already formally initiated in the early work of Bogdanov, Obata, and Trevisan [ BOT02 ] , who showed that, beyond the specific case of \mathsf{3COL} , several other CSPs (such as \mathsf{3SAT} and \mathsf{3LIN} ) require \Omega(n) queries to test in this model. A more systematic investigation was later carried out by Yoshida [ Yos11 ] , who proved that any CSP robustly solved by BasicLP (the basic linear program) has a satisfiability tester that makes a constant number of queries. Typical examples of such CSPs include \mathsf{1SAT} and \mathsf{3HornSAT} . For the satisfiability testing of any CSP that is not solved by BasicLP , [ Yos11 ] further showed that at least \Omega(\sqrt{n}) queries are necessary. Examples of such CSPs include \mathsf{2SAT} and \mathsf{2COL} . 3 3 3 Robust