  Consider the family of bounded degree graphs in any minor-closed family (such
as planar graphs). Let d be the degree bound and n be the number of vertices of
such a graph. Graphs in these classes have hyperfinite decompositions, where,
for a sufficiently small \e > 0, one removes \edn edges to get connected
components of size independent of n. An important tool for sublinear algorithms
and property testing for such classes is the partition oracle, introduced by
the seminal work of Hassidim-Kelner-Nguyen-Onak (FOCS 2009). A partition oracle
is a local procedure that gives consistent access to a hyperfinite
decomposition, without any preprocessing. Given a query vertex v, the partition
oracle outputs the component containing v in time independent of n. All the
answers are consistent with a single hyperfinite decomposition. The partition
oracle of Hassidim et al. runs in time d^poly(d/\e) per query. They pose the
open problem of whether poly(d/\e)-time partition oracles exist. Levi-Ron
(ICALP 2013) give a refinement of the previous approach, to get a partition
oracle that runs in time d^{\log(d/\e)-per query. In this paper, we resolve
this open problem and give \poly(d/\e)-time partition oracles for bounded
degree graphs in any minor-closed family. Unlike the previous line of work
based on combinatorial methods, we employ techniques from spectral graph
theory. We build on a recent spectral graph theoretical toolkit for
minor-closed graph families, introduced by the authors to develop efficient
property testers. A consequence of our result is a poly(d/\e)-query tester for
any monotone and additive property of minor-closed families (such as bipartite
planar graphs). Our result also gives poly(d/\e)-query algorithms for additive
{\e}n-approximations for problems such as maximum matching, minimum vertex
cover, maximum independent set, and minimum dominating set for these graph
families.
