Random walks and forbidden minors II
Akash S. Kumar, Comandur Seshadhri, Andrew Stolman · 2019
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 (dε−1), even for planarity.