Search Mailing List Archives
[theory-seminar] Theory Lunch -- Andrew Stolman (UCSC)
Reyna Marie Hulett
rmhulett at stanford.edu
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!
----------------------------------------
Abstract:
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 https://arxiv.org/abs/1805.08187.
Joint work with C. Seshadhri of UCSC and Akash Kumar of Purdue University.
----------------------------------------
Cheers,
-Reyna
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20181030/03ea9abe/attachment-0003.html>
More information about the theory-seminar
mailing list