Partitioning a graph into two (or more) large pieces while minimizing
the size of the ``interface'' between them is a fundamental
combinatorial problem. Graph partitions or separators are central
objects of study in the theory of Markov chains, geometric embeddings
and are a natural algorithmic primitive in numerous settings, including
clustering, divide and conquer approaches, PRAM emulation, VLSI layout,
and packet routing in distributed networks. Most versions of graph
partitioning are NP-hard, so researchers have tried to develop
approximation algorithms.

The past year has seen a flurry of new approximation algorithms,
starting with a paper of mine with Satish Rao and Umesh Vazirani in
STOC'04 that gave a \sqrt{log n}-approximation for SPARSEST CUT. This
improved classical algorithms based upon both spectral methods and
multicommodity flows (Leighton Rao 1988; O(log n)-approximation). We
also introduced the notion of expander flows, which constitute an
interesting ``certificate'' of a graph's expansion.

The [ARV] algorithm used semidefinite programming and hence was not too
efficient. In joint work with Hazan and Kale (FOCS'04) we give a more
combinatorial algorithm. It runs in near-quadtratic time, raising hopes
of practical impact.

Finally, the ideas used in the [ARV] approximation algorithm have led
to sudden progress in another research area: low-distortion embeddings
of finite metric spaces into geometric spaces (such as l_2). Recent
unpublished papers (Chawla, Gupta, Racke; improved upon in my joint work
with Lee and Naor) show how to embed n-point subsets of l_1 into l_2
with distortion much better than Bourgain's bound of O(log n) from 1985.
Thus algorithmic ideas have helped resolve questions in pure mathematics.

The talk will be a self-contained survey of the above results, as well
as several papers not mentioned above.