University of Cambridge > > Kuwait Foundation Lectures > The local theory of metric spaces and graph algorithms

The local theory of metric spaces and graph algorithms

Add to your list(s) Download to your calendar using vCal

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 L _1, which has been solved by Bourgain in 1986. We will then proceed to study a quadratic variant of this approach which leads to the best known approximation algorithm for the Sparsest Cut problem. The investigation of this “semidefinite relaxation” leads to delicate questions in metric geometry and isoperimetry, in which the geometry of the Heisenberg group plays an unexpected role.

This talk is part of the Kuwait Foundation Lectures series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity