Zum Inhalt springen

Nur-Lesen-Fassung: Das Forschungsinformationssystem (FIS) ist aus Sicherheitsgründen vorübergehend durch diese Nur-Lesen-Fassung ersetzt. Alle öffentlichen Inhalte und Volltexte sind weiterhin abrufbar; Anmeldung, Bearbeitung, Einreichung und Statistiken stehen nicht zur Verfügung. Bei Fragen: fis@uni-bamberg.de

Start › Publikationen › On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing

Publikation

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: Bamberg: Otto-Friedrich-Universität, S. 1–69.

Details

Fakultät/Lehrstuhl
Autorin(nen)/Autor(en)
Köhler, Noleen
Peng, Pan
Verlagsangabe
Otto-Friedrich-Universität : Bamberg
Erscheinungsjahr
2023
Quelle/Weitere Ausgabe
Online : arXiv, 2023, S. 1-69, doi: 10.48550/arxiv.2304.03810.
Jahr der Erstpublikation
2023
Sprache(n)
Englisch
Lizenz
URN
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.

GND-Schlagwort(e)
Prädikatenlogik erster Stufe
Nachbarschaftsgraph
Lokalität <Informatik>
Untere Schranke
Freie Schlagwort(e)
Graph property testing
first-order logic
proximity-oblivious testing
locality
lower bound
DDC-Klassifikation
004 Computer science
500 Naturwissenschaften
RVK-Klassifikation
SK 130
Dokumenttyp
preprint
URI
Datum der Freischaltung
05.10.2023

Permalink: https://fis.uni-bamberg.de/handle/uniba/91019 · Daten als JSON · Zitieren: BibTeX · RIS

Datenstand: 15.11.2026

Eingeschränkter Lesezugriff: Anmeldung, Bearbeitung und Einreichung sind vorübergehend deaktiviert.