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