2019/04/01 by Kumar, Akash, Seshadhri, C., Stolman, Andrew
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1904.01055
Let G be a graph with n vertices and maximum degree d. Fix some minor-closed property P (such as planarity). We say that G is ε-far from P if one has to remove ε dn edges to make it have P. The problem of property testing P 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.