  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
$\text{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 \text{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.
