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] Amin speaking in combinatorics seminar

Gregory Valiant gvaliant at
Wed Oct 7 12:56:20 PDT 2015

Hi Everyone,
Amin will be talking at tomorrow's combinatorics seminar about some
cool graph theory/combinatorics that is very relevant to problems in
tcs.  title/abstract/time/place below.

Amin Saberi (Stanford), Thin spanning trees and their algorithmic applications
When: Thu, October 8, 3pm – 4pm
Where: 384-H (math building, fourth floor)

Abstract:  Motivated by Jaeger's modular orientation conjecture,
Goddyn asked the following question:

A spanning tree of a graph G is called epsilon-thin if it contains at
most an epsilon fraction of the edges of each cut in that graph. Is
there a function f:(0,1)→ℤ such that every f(epsilon)-edge-connected
graph has an epsilon-thin spanning tree?

I will talk about our journey in search of such thin trees, their
applications concerning traveling salesman problems, and unexpected
connections to graph sparsification and the Kadison-Singer problem.

More information about the theory-seminar mailing list