Sparsest Cut, discrete differentiation, and local rigidity of sets in the plane
ABSTRACT: I will briefly recall the connection between the Sparsest Cut problem in graphs and low-distortion embeddings of finite metric spaces into L_1. 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 L_1-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 L_1, 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.
BIO: James Lee is an Associate Professor at the Department of Computer Science and Engineering, University of Washington. He received a PhD in CS from Berkeley, advised by Christos Papadimitriou. After a postdoc in Avi Wigderson's group at the Institute for Advanced Study in Princeton he joined UW. He is visiting MSR this fall. More details and James’ papers can be found at http://www.cs.washington.edu/homes/jrl/