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 > Kuwait Foundation Lectures > The local theory of metric spaces and graph algorithms

## The local theory of metric spaces and graph algorithmsAdd to your list(s) Download to your calendar using vCal - Professor A. Naor (Microsoft Research and Courant Institute)
- Tuesday 13 February 2007, 17:00-18:00
- Wolfson Room (MR 2) Centre for Mathematical Sciences, Wilberforce Road, Cambridge.
If you have a question about this talk, please contact helen. In the past decade methods from Riemannian geometry and Banach space theory have become a central tool in the design and analysis of approximation algorithms for a wide range of NP hard problems. In the reverse direction, problems and methods from theoretical computer science have recently led to solutions of long standing problems in metric geometry. This talk will illustrate the connection between these fields through the example of the Sparsest Cut problem. This problem asks for a polynomial time algorithm which computes the Cheeger constant of a given finite graph. The Sparsest Cut problem is known to be NP hard, but it is of great interest to devise efficient algorithms which compute the Cheeger constant up to a small multiplicative error. We will show how a simple linear programming formulation of this problem leads to a question on bi-Lipschitz embeddings of finite metric spaces into This talk is part of the Kuwait Foundation Lectures series. ## This talk is included in these lists:- All CMS events
- All Talks (aka the CURE list)
- CMS Events
- DPMMS Lists
- DPMMS Pure Maths Seminar
- DPMMS info aggregator
- DPMMS lists
- Discrete Analysis Seminar
- Hanchen DaDaDash
- Interested Talks
- Kuwait Foundation Lectures
- School of Physical Sciences
- Wolfson Room (MR 2) Centre for Mathematical Sciences, Wilberforce Road, Cambridge
- bld31
Note that ex-directory lists are not shown. |
## Other listsNext Genration Biophysics; Friday 8th November 2019 Churchill Undergraduate Physics Seminars https://data.mendeley.com/.../48a01efd-27c7-4835-9f51-f73c2978... Traduire cette page 7 nov. 2016 - Boudemagh, N (2016), “Applied statistics”, Mendeley Data, v1 http://dx.doi.org/10.17632/6p462pvms6.1#file-48a01efd-27c7-4835-9f51- ...## Other talksFormation and disease relevance of axonal endoplasmic reticulum, a "neuron within a neuron”. Dynamics of Phenotypic and Genomic Evolution in a Long-Term Experiment with E. coli What quantum computers tell us about physics (even if no one ever builds one!) Primary liver tumor organoids: a new pre-clinical model for drug sensitivity analysis CANCELED DUE TO USS PENSIONS STRIKE. An SU(3) variant of instanton homology for webs Fields of definition of Fukaya categories of Calabi-Yau hypersurfaces The Digital Doctor: Hope, Hype, and Harm at the Dawn of Medicine’s Computer Age Symplectic topology of K3 surfaces via mirror symmetry The Gopakumar-Vafa conjecture for symplectic manifolds Assessment of data completeness in the National Cancer Registry and the impact on the production of Cancer Survival Statistics |