## 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] TCS+ talk: Wednesday, October 17, C. Seshadhri, UC Santa Cruz

Clément Canonne ccanonne at cs.stanford.edu
Tue Oct 16 11:18:54 PDT 2018

```Reminder: this is *tomorrow morning*. With pastries, and resolution of
an eight-year old conjecture.

-- Clément

On 10/11/18 1:25 PM, Clément Canonne wrote:
> 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
>
> _______________________________________________
> theory-seminar mailing list
> theory-seminar at lists.stanford.edu
> https://mailman.stanford.edu/mailman/listinfo/theory-seminar

```