## Columbia Mathematics Department Colloquium

*"The story of the Sparsest Cut problem"*

### by

### Assaf Naor

### Courant
Institute, NYU

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**