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.
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.