Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch -- Andrew Stolman (UCSC)

Reyna Marie Hulett rmhulett at
Tue Oct 30 13:28:17 PDT 2018

Hi everybody,

This week's theory lunch will be given by Andrew Stolman (UCSC) on “Finding forbidden minors through random walks: an almost optimal one-sided tester for minor-closed properties”--see abstract below. As always, please join us Thursday from noon to 1 pm in Gates 463A!

Let [G]  be an undirected, bounded degree graph with  vertices. Fix a finite graph [H] , and suppose one must remove  edges from [G]  to make it [H] -minor-free (for some small constant [\varepsilon > 0] ). We give an n1/2 + o(1)-time randomized algorithm that, with high probability, finds an [H] -minor in such a graph. As an application, suppose one must remove  edges from a bounded degree graph [G]  to make it planar. This result implies an algorithm, with the same running time, that produces a [K_{3,3}]  or [K_5]  minor in [G] . No prior sublinear time bound was known for this problem.

By the graph minor theorem, we get an analogous result for any minor-closed property. Up to [n^{o(1)}]  factors, this resolves a conjecture of Benjamini-Schramm-Shapira (STOC 2008) on the existence of one-sided property testers for minor-closed properties. Furthermore, our algorithm is nearly optimal, by an [\Omega(\sqrt{n})]  lower bound of Czumaj et al (RSA 2014).

This result appeared in FOCS 2018 and the paper can be found here

Joint work with C. Seshadhri of UCSC and Akash Kumar of Purdue University.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list