Noleen Köhler, Testing first-order definable properties on bounded degree graphs

Property testers are probabilistic algorithms aiming to solve a decision problem efficiently in the context of big-data. A property tester for a property P has to decide (with high probability correctly) whether a given input graph has property P or is far from having property P while having local access to the graph. We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree model. We show that any FO property that is defined by a formula with quantifier prefix ∃*∀* is testable, while there exists an FO property that is expressible by a formula with quantifier prefix ∀*∃* 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 a first-order formula that defines a class of bounded-degree expanders, based on zig-zag products of graphs.

This is joint work with Isolde Adler and Pan Peng.