Abstract:
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.
.
January 28th,
Wednesday, 5:00-6:00 pm
Mathematics 520
Tea will be served at 4:30pm