COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Discrete differentiation and local rigidity of smooth sets in the plane

## Discrete differentiation and local rigidity of smooth sets in the planeAdd to your list(s) Download to your calendar using vCal - Sidiropoulos, A (Toyota Technological Institute)
- Tuesday 11 January 2011, 10:00-11:00
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Discrete Analysis 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). This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listscms-all@maths.cam.ac.uk Evolution International Political Theory Research Seminar Series## Other talksTying Knots in Wavefunctions Development of a Broadly-Neutralising Vaccine against Blood-Stage P. falciparum Malaria Ribosome profiling and virus infection CANCELLED - Methodology Masterclass: Exploring the pedagogic possibilities of new diaspora formations and transnationalism. Auxin and cytokinin regulation of root architecture - antagonism or synergy Epigenetics: One Genome, Multiple Phenotypes |