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.

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.