This paper resolves one of my treasured open problems, albeit in a direction opposite to the one I have conjectured and hoped for. The issue is the characterization of graph properties that have a proximity-oblivious tester (POT) in the bounded-degree graph model. The known characterization assert that this class equals the class of generalised subgraph freeness (GSF) properties that satisfy an auxiliary condition called non-propagation. I conjectured that all GSF properties satisfy this condition, and was reluctant to refer to the foregoing as a satisfactory characterization (due to the annoying auxiliary condition). However, the current paper proved me wrong. In fact, their main result is stronger: It asserts that there exist GSF properties that cannot be tested (in the bounded-degree graph model) within size-oblivious query complexity (i.e., complexity that only depends on the proximity parameter).
Added on Jan 2024: my digest.
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.
Available from arxiv.