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

[Reyna Marie Hulett]

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>