Abstract
In the field of property testing, a central challenge is characterizing which graph properties can be tested efficiently in the bounded-degree model. A decade-old conjecture suggested that GSF-locality—the property of being defined by a set of forbidden local configurations—might be sufficient to guarantee the existence of a proximity-oblivious tester (POT). This paper resolves that conjecture in the negative. By constructing a GSF-local property that exhibits "propagation"—where local violations necessitate global structural changes—the authors demonstrate that locality alone does not imply constant-query testability.
Introduction
Property testing seeks to determine whether a massive object (such as a graph) satisfies a specific property or is "far" from satisfying it, using only a constant number of local queries. Within the bounded-degree model, researchers have long sought a combinatorial characterization of testable properties.
A particularly elegant class of algorithms is the Proximity-Oblivious Tester (POT). Unlike standard testers, a POT’s basic sub-routine is independent of the proximity parameter $\epsilon$. In 2009, Goldreich and Ron established that for a property to admit a POT, it must be GSF-local (generalized subgraph freeness) and satisfy a "non-propagation" condition. They posed a fundamental question: Is every GSF-local property inherently non-propagating? If so, GSF-locality would be the definitive hallmark of proximity-oblivious testability. This research proves that this is not the case.
Theoretical Framework: FO Logic and Locality
To bridge the gap between descriptive complexity and query complexity, the authors utilize First-Order (FO) logic. According to Gaifman’s and Hanf’s Theorems, properties expressible in FO logic are inherently local, as the truth of an FO sentence depends only on the frequencies of local neighborhood types.
The authors introduce the concept of neighbourhood profiles, which count the occurrences of specific local isomorphism types. A critical technical contribution is the identification of "0-profiles"—profiles that define a property by forbidding certain local configurations (setting their allowed count to zero). The paper proves that any FO property defined by a union of 0-profiles is GSF-local, providing a formal link between logical expressibility and the GSF-locality required for POTs.
The Counterexample: Propagation in Local Structures
The heart of the paper is the construction of a GSF-local property that is impossible to test with a constant number of queries. The authors build upon a complex structure involving a tree where each level is composed of an expander graph.
While this structure is FO-definable (and thus local), it is "propagating." In a propagating property, a single local violation cannot be fixed in isolation; attempting to correct a local patch triggers a chain reaction that requires modifying a linear fraction of the graph's edges. This global dependency ensures that a tester cannot reliably detect distance from the property by looking at a constant-sized neighborhood.
Using a local reduction, the authors transform this relational expander-tree structure into a standard graph property. They demonstrate that this property remains GSF-local but lacks the non-propagation characteristic necessary for efficient testing.
Key Results and Implications
The primary contribution of this work is the formal resolution of Goldreich and Ron's Open Question 2.6:
- Theorem 1.1: There exists a GSF-local property in the bounded-degree model that is not testable with a constant number of queries.
- Negative Resolution: The result confirms that GSF-locality is a necessary, but not sufficient, condition for proximity-oblivious testing.
This finding shifts the focus of the field. It suggests that the "Holy Grail" of property testing—a complete characterization of testable properties—must look beyond simple local forbidden configurations and account for the global structural implications of those local constraints.
Conclusion
By proving that locality does not equate to testability, this paper clarifies the boundaries of the bounded-degree model. The introduction of 0-profiles and the connection between FO logic and GSF-locality provide a new mathematical toolkit for future researchers. While the search for a full characterization of testability continues, this work definitively narrows the search space by decoupling the concepts of local definition and local testability.
Summary updated