Columbia Mathematics Department Colloquium


"The story of the Sparsest Cut problem"


 Assaf Naor  

Courant Institute, NYU


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