TCS+ talk: Wednesday, October 17 — C. Seshadhri, UC Santa Cruz
The next TCS+ talk will take place this coming Wednesday, October 17th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). C. Seshadhri from UC Santa Cruz will speak about “Finding forbidden minors through random walks: (almost) -query one-sided testers for minor closed properties” (abstract below).
Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.
Abstract: Let be an undirected, bounded degree graph with vertices. Fix a finite graph , and suppose one must remove edges from to make it -minor free (for some small constant ). We give a nearly time algorithm that, with high probability, finds an -minor in such a graph.
As an application, consider a graph that requires edge removals to make it planar. This result implies an algorithm, with the same running time, that produces a or minor in . 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 factors, this result 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 lower bounds of Czumaj et al (RSA 2014).
Joint work with Akash Kumar and Andrew Stolman