Logical methods for property testing in the bounded degree model

Property testers are randomised sublinear time algorithms which infer global structure from
a local view of an input. In the context of bounded degree graphs, testability of a property is
tightly linked to the question of whether an approximate distribution of r-neighbourhood types
of a graph is sufficient to capture whether the graph has the property or is “far” from having
the property. Our understanding of when this is the case is limited. The central open question
in the field of property testing is to characterise testable properties of bounded degree graphs.
Towards a characterisation of testable properties in the bounded degree model, we study
property testing of properties definable in first-order logic (FO) in the bounded degree model.
By Gaifman’s locality theorem it is known that FO can only express local properties. On the
other hand, testers can explore only local neighbourhoods and hence locality is necessary for
testability. We prove however, that the notion of locality imposed by being definable in FO is
not sufficient for property testing. More precisely, we show that there is a non-testable property
defined by an FO-sentence whose quantifier prefix contains only one quantifier alternation of the
form “∀∃”. We complement this by proving that every FO-sentence not containing a quantifier
alternation of the form “∀∃” can be tested with a constant number of queries. We further
identify some classes of FO-sentences which yield testable properties and contain quantifier
alternations of the form “∀∃”. These sentences express that the distribution of r-neighbourhood
types is of a particular, simple form.
We explore the connection between the notion of locality imposed by FO and the notion
of locality necessary for testability further. We establish links between FO definability and a
generalised notion of subgraph freeness. This notion was introduced in the context of character-
ising one-sided error proximity oblivious testers, a particularly simple type of testers. Using a
variation of our non-testable FO definable property we show that generalised subgraph freeness
does equally not capture the locality needed for testability, which answers an open question
regarding the characterisation of testable properties in the bounded degree model.
Going beyond FO definability, we explore hardness of property testing problems in connec-
tion with classical complexity theory. We obtain a deterministic construction of hard instances
for property testing Hamiltonicity, which is a known non-testable property. This construc-
tion is interesting from the perspective of exploring links between structural properties and
non-testability. We further utilise the lower bound technique developed in the context of our
non-testable FO definable property to prove non-testability of having treewidth logarithmic in
the number of vertices.