Speaker James Lee
Host Yuval Peres
Affiliation University of Washington
Date recorded 29 September 2011
I will briefly recall the connection between the Sparsest Cut problem in graphs and low-distortion embeddings of finite metric spaces into L1. Then I will talk about a recent approach to lower bounds pioneered by Cheeger and Kleiner (2006), following a conjecture we made with Naor (2003). The main idea is to develop a differentiation theory for L1-valued mappings. I will discuss a discrete version of this theory (following Eskin-Fisher-Whyte and Lee-Raghavendra).
I will then construct a doubling space whose n-point subsets rqeuire bi-lipschitz distortion ~ (log n)1/2 to embed into L1, matching the upper bound of Gupta-Krauthgamer-Lee (2003), and improving over the (log n)c bound of Cheeger, Kleiner, and Naor (2009). This leads to nearly tight integrality gaps for some well studied semi-definite program relaxations. Our lower bound space, developed jointly with Sidiropoulos, takes inspiration from both the 3-dimensional Heisenberg group and the diamond graphs. The main technical difficulty involves approximately classifying certain weakly regular sets in the plane, a problem in "approximate" integral geometry that may be independently interesting.
©2011 Microsoft Corporation. All rights reserved.