Options
On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing
Adler, Isolde; Köhler, Noleen; Peng, Pan (2023): On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing, in: Online: arXiv, S. 1–69, doi: 10.48550/arxiv.2304.03810.
Faculty/Chair:
Author:
Publisher Information:
Year of publication:
2023
Pages:
Language:
English
Abstract:
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 ∃∗∀∗ is testable (i.e., testable with constant query complexity), 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 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.
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.
GND Keywords: ; ; ;
Prädikatenlogik erster Stufe
Nachbarschaftsgraph
Lokalität <Informatik>
Untere Schranke
Keywords: ; ; ; ;
Graph property testing
first-order logic
proximity-oblivious testing
locality
lower bound
DDC Classification:
RVK Classification:
Type:
Preprint
Activation date:
August 22, 2023
Versioning
Question on publication
Permalink
https://fis.uni-bamberg.de/handle/uniba/90093