2026-07-28T19:12:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14308 2024-03-06T10:53:56Z ddc:004 open_access

GSF-Locality Is Not Sufficient For Proximity-Oblivious Testing Adler, Isolde Köhler, Noleen Peng, Pan Property testing proximity-oblivous testing locality first-order logic lower bound 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Isolde Adler and Noleen Köhler and Pan Peng 2021 Is Part Of LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2021.34 urn:nbn:de:0030-drops-143082 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.34 eng https://creativecommons.org/licenses/by/4.0/legalcode