[theory-seminar] Amin speaking in combinatorics seminar

[Gregory Valiant]

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.
-g

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.