Abstract

We exhibit an infinite doubling metric space whose n-point subsets require distortion sqrt(log n/log log n) to embed into L_1. This nearly matches the upper bound of sqrt(log n) (Gupta-Krauthgamer-Lee 2003) and improves over the best previous bound of (log n)^c for some c > 0 (Cheeger-Kleiner-Naor 2009). Furthermore, this offers a nearly tight integrality gap for a weak version of the Goemans-Linial SDP for Sparsest Cut, matching the upper bound of Arora-Lee-Naor (2005). We discuss how our results might lead to a resolution of the full Goemans-Linial conjecture.

Following the general approach developed by Cheeger and Kleiner (2006), our lower bound uses a differentiation argument to achieve local control on the cut measure, followed by a classification step of the cuts that can appear. In order to get tight bounds, the classification step has to deal with sets which satisfy only a weak average regularity assumption, meaning that we have to control not just “99%-structured sets,” but “1%-structured” sets as well. This weak regularity is achieved via a random differentiation argument which measures the variation of the function along randomly chosen subdivisions of geodesics.

Our lower bound space is a 2-dimensional complex which takes inspiration from both the Heisenberg group and the diamond graphs.

This is joint work with James R. Lee (University of Washington).