Sparsest Cut, Discrete Differentiation, and Local Rigidity of Sets in the Plane

Speaker  James Lee

Host  Yuval Peres

Affiliation  University of Washington

Duration  00:52:01

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.
> Sparsest Cut, Discrete Differentiation, and Local Rigidity of Sets in the Plane