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

I will briefly recall the connection between the Sparsest Cut problem in graphs and low-distortion embeddings of finite metric spaces into L₁. 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₁-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₁, 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.