BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Discrete differentiation and local rigidity of smooth sets in the 
 plane - Sidiropoulos\, A (Toyota Technological Institute)
DTSTART:20110111T100000Z
DTEND:20110111T110000Z
UID:TALK28834@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:We exhibit an infinite doubling metric space whose n-point sub
 sets\nrequire distortion sqrt(log n/log log n) to embed into L_1.  This\nn
 early matches the upper bound of sqrt(log n) (Gupta-Krauthgamer-Lee 2003)\
 nand improves over the best previous bound of (log n)^c for some c > 0\n(C
 heeger-Kleiner-Naor 2009).  Furthermore\, this offers a nearly tight\ninte
 grality 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 r
 esults might lead to a resolution of the full Goemans-Linial conjecture.\n
 \nFollowing 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 ca
 n appear. In order to get tight bounds\, the classification step has to de
 al with sets which satisfy only a weak average regularity assumption\, mea
 ning that we have to control not just "99%-structured sets\," but "1%-stru
 ctured" sets as well.  This weak regularity is achieved via a random diffe
 rentiation\nargument which measures the variation of the function along ra
 ndomly chosen subdivisions of geodesics.\n\nOur lower bound space is a 2-d
 imensional complex which takes inspiration from both the Heisenberg group 
 and the diamond graphs.\n\nThis is joint work with James R. Lee (Universit
 y of Washington).\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR