### Discrete differentiation and local rigidity of smooth sets in the plane

Sidiropoulos, A *(Toyota Technological Institute)*

Tuesday 11 January 2011, 10:00-11:00

Seminar Room 1, Newton Institute

#### 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).

#### Presentation

#### Video

**The video for this talk should appear here if JavaScript is enabled.**

If it doesn't, something may have gone wrong with our embedded player.

We'll get it fixed as soon as possible.

## Comments

Start the discussion!