## Random walks and forbidden minors II: A $\poly(d\eps^{-1})$-query
tester for minor-closed properties of bounded degree graphs

by Akash Kumar, C. Seshadhri, and Andrew Stolman

#### Oded's comments

Immediate reaction: I haven't looked at the technical ideas yet,
but am excited enough about the result to post this choice immediately.

After reading the technical overview (Sec. 1.2):
The basic idea is to imagine an execution of the tester of the
prior paper on a graph $G'$ that has small
(i.e., $\poly(1/\eps)$ size) connected components that
is $\eps/2$-close to the given graph $G$,
while observing that this tester (which is actually invoked on $G$)
is unlikely to traverse an edge that was omitted from $G$.
Such a graph $G'$ (which corresponds to a *partition oracle*)
definitely exists in case $G$ is minor free,
and the tester will find a suitable minor
in case $G'$ is $\eps/2$-far from being minor free.
On the other hand, if no such $G'$ exists, then this fact will be
detected by the collision of the random paths taken by the tester
(which is below the threshold when $G$ is minor-free).

Note that the foregoing tester avoids the task of implementing
a good partition oracle (in case the graph is minor-free),
but rather relies on the fact that such a partition exists
(in that case). Hence, the problem of implementing such
an oracle using $\poly(1/\eps)$ queries remains open.

#### The original abstract

Let $G$ be a graph with $n$ vertices and maximum degree $d$. Fix some
minor-closed property $\mathcal{P}$ (such as planarity).
We say that $G$ is $\varepsilon$-far from $\mathcal{P}$ if one has to
remove $\varepsilon dn$ edges to make it have $\mathcal{P}$.
The problem of property testing $\mathcal{P}$ was introduced
in the seminal work of Benjamini-Schramm-Shapira (STOC 2008) that gave
a tester with query complexity triply exponential in $\varepsilon^{-1}$.
Levi-Ron (TALG 2015) have given the best tester to date, with a
quasipolynomial (in $\varepsilon^{-1}$) query complexity.
It is an open problem to get property testers whose query complexity
is $\poly(d\varepsilon^{-1})$, even for planarity.

In this paper, we resolve this open question. For any minor-closed property,
we give a tester with query complexity $d\cdot \poly(\varepsilon^{-1})$.
The previous line of work on (independent of $n$, two-sided) testers is
primarily combinatorial.
Our work, on the other hand, employs techniques from spectral graph theory.
This paper is a continuation of recent work of
the authors (FOCS 2018)
analyzing random walk algorithms that find forbidden minors.

See ECCC TR19-046.

Back to
list of Oded's choices.