Search Mailing List Archives
[theory-seminar] TCS+ talk: Wednesday, October 17, C. Seshadhri, UC Santa Cruz
Clément Canonne
ccanonne at cs.stanford.edu
Thu Oct 11 13:25:25 PDT 2018
Hi everyone,
Next Wednesday, we'll have a TCS+ talk in Gates 463A: we'll be watching
Sesh (UCSC) talk about a recent result on efficiently finding forbidden
minors through random walks in graphs (title and abstract below).
it's as usual at 9:55am: come for the breakfast, stay for the
K_{3,3}-minor finding!
Best,
-- Clément
-------------------------------
Speaker: C. Seshadhri (UC Santa Cruz)
Title: Finding forbidden minors through random walks: (almost) n^{1/2}
query one-sided testers for minor closed properties
Abstract: Let G be an undirected, bounded degree graph with n vertices.
Fix a finite graph H, and suppose
one must remove eps*n edges from G to make it H-minor free (for some
small constant eps > 0). We give a nearly n^{1/2} time algorithm that,
with high probability, finds an H-minor in such a graph.
As an application, consider a graph G that requires eps*n edge removals
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 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
More information about the theory-seminar
mailing list