## GSF-locality is not sufficient for proximity-oblivious testing

by Isolde Adler, Noleen Kohler, and Pan Peng

#### Oded's comments

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.

#### The original 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.

Available from
arxiv.

Back to
list of Oded's choices.