BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The local theory of metric spaces and graph algorithms - Professor
  A. Naor (Microsoft Research and Courant Institute)
DTSTART:20070213T170000Z
DTEND:20070213T180000Z
UID:TALK6454@talks.cam.ac.uk
CONTACT:4993
DESCRIPTION:In the past decade methods from Riemannian geometry and Banach
  space theory have become a central tool in the design and analysis of app
 roximation algorithms for a wide range of NP hard problems. In the reverse
  direction\, problems and methods from theoretical computer science have r
 ecently led to solutions of long standing problems in metric geometry. Thi
 s talk will illustrate the connection between these fields through the exa
 mple 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 i
 n 1986. We will then proceed to study a quadratic variant of this approach
  which leads to the best known approximation algorithm for the Sparsest Cu
 t problem. The investigation of this "semidefinite relaxation" leads to de
 licate questions in metric geometry and isoperimetry\, in which the geomet
 ry of the Heisenberg group plays an unexpected role.
LOCATION:Wolfson Room (MR 2) Centre for Mathematical Sciences\, Wilberforc
 e Road\, Cambridge
END:VEVENT
END:VCALENDAR