  We study property testing of properties that are definable in first-order
logic (FO) in the bounded-degree graph and relational structure models. We show
that any FO property that is defined by a formula with quantifier prefix
$\exists^*\forall^*$ is testable (i.e., testable with constant query
complexity), while there exists an FO property that is expressible by a formula
with quantifier prefix $\forall^*\exists^*$ that is not testable. In the dense
graph model, a similar picture is long known (Alon, Fischer, Krivelevich,
Szegedy, Combinatorica 2000), despite the very different nature of the two
models. In particular, we obtain our lower bound by an FO formula that defines
a class of bounded-degree expanders, based on zig-zag products of graphs. We
expect this to be of independent interest.
  We then use our class of FO definable bounded-degree expanders to answer a
long-standing open problem for proximity-oblivious testers (POTs). POTs are a
class of particularly simple testing algorithms, where a basic test is
performed a number of times that may depend on the proximity parameter, but the
basic test itself is independent of the proximity parameter. In their seminal
work, Goldreich and Ron [STOC 2009; SICOMP 2011] show that the graph properties
that are constant-query proximity-oblivious testable in the bounded-degree
model are precisely the properties that can be expressed as a generalised
subgraph freeness (GSF) property that satisfies the non-propagation condition.
It is left open whether the non-propagation condition is necessary. We give a
negative answer by showing that our property is a GSF property which is
propagating. Hence in particular, our property does not admit a POT. For this
result we establish a new connection between FO properties and GSF-local
properties via neighbourhood profiles.
