GSF-locality is not sufficient for proximity-oblivious testing

DOI10.4230/LIPICS.CCC.2021.34arXiv2105.08490OpenAlexW3185138001MaRDI QIDQ6115397FDOQ6115397

Authors: Isolde Adler, Noleen Köhler, Pan Peng 

Publication date: 12 July 2023

Abstract: In Property Testing, proximity-oblivious testers (POTs) form 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 allow constant-query proximity-oblivious testing 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. Indeed, calling properties expressible as a generalised subgraph freeness property GSF-local properties, they ask whether all GSF-local properties are non-propagating. We give a negative answer by exhibiting a property of graphs that is GSF-local and propagating. Hence in particular, our property does not admit a POT, despite being GSF-local. We prove our result by exploiting a recent work of the authors which constructed a first-order (FO) property that is not testable [SODA 2021], and a new connection between FO properties and GSF-local properties via neighbourhood profiles.

Full work available at URL: https://arxiv.org/abs/2105.08490

Recommendations

• On Proximity-Oblivious Testing
• Proximity oblivious testing and the role of invariances
• Proximity Oblivious Testing and the Role of Invariances
• On proximity oblivious testing
• scientific article; zbMATH DE number 7650374
• Reducing the time complexity of testing for local threshold testability
• Reducing the time complexity of testing for local threshold testability
• Two-sided error proximity oblivious testing (extended abstract)
• 2-transitivity is insufficient for local testability
• Locally Testable Codes Require Redundant Testers

zbMATH Keywords

lower boundfirst-order logicproperty testinglocalityproximity-oblivous testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (3)

• On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing
• Proximity Oblivious Testing and the Role of Invariances
• On Proximity-Oblivious Testing

This page was built for publication: GSF-locality is not sufficient for proximity-oblivious testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6115397)