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

Опубликовано 17 августа 2016, 3:28

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.