[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

*THEORY SEMINAR REMINDER*
 
Nick Harvey
Assistant Professor
University of British Columbia
 
Tuesday, May 6, 2014
3:00 pm
Ryerson 251
Title: “Spectrally Thin Trees”
 
Abstract:
Thin trees are intriguing objects in graph theory that relate to foundational topics, such as nowhere-zero flows and the asymmetric traveling salesman problem (ATSP). A spanning subtree T of a graph G is called alpha-thin if every cut in T contains at most an alpha-fraction of G's edges in that cut.
 
Asadpour et al gave an algorithm constructing an O(log n / k log log n)-thin tree in any graph with n vertices and edge-connectivity k. Improving this to O(1/k) would imply a constant-factor approximation algorithm for ATSP.
 
We define a stronger notion of thinness that is naturally motivated by spectral sparsification of graphs. A spanning subtree T of G is called alpha-spectrally-thin if T's Laplacian matrix is upper-bounded by alpha times G's Laplacian matrix in the Lowner ordering.
 
We give a deterministic, polynomial time algorithm to construct an O (log n / c log log n)-spectrally thin tree in any graph with n vertices and for which the effective conductance across each edge is at least c.
 
Remarkably, this can be improved to O(1/c) if one does not require an efficient algorithm. The recent breakthrough results of Marcus, Spielmanand Srivastava imply the existence of a O(1/c)-spectrally-thin tree.
 
This is joint work with Neil Olver (MIT / Vrije Universiteit). 
 
Host: Prof.Alexander Razborov
Refreshments will be served prior to the talk at 2:30 in Ry. 255
For additional information on future CS /Theory talks please visit: http://www.cs.uchicago.edu/events

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140506/f68926d8/attachment.htm