Back to search

University of Leeds

Logical methods for property testing in the bounded degree model

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Leeds
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Köhler, Noleen
Advisors dc:contributor.advisor
  • Adler, Isolde
  • Kristina, Vuskovic

Rights

Language dc:language.dcterms_iso639_2
eng

Identifiers

dc:identifier.*
Identifier
uk.bl.ethos.837108

Chain of custody

source
Harvested from
White Rose University Consortium
Base URL
etheses.whiterose.ac.uk/cgi/oai2
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Köhler, Noleen. Logical methods for property testing in the bounded degree model. doctoral thesis, University of Leeds, 2021.