Fast algorithms for Balanced Separator by simulating random walks

The goal of the Balanced Separator problem is to cut a graph into two
roughly equal parts, while minimizing the number of edges cut. It is a
fundamental problem, both in theory and practice. Given the massive
size of several graphs of interest today (e.g. the web graph), we
would like near-linear time algorithms for this problem. In this talk,
we present the first such algorithm with an approximation guarantee
that's optimal for spectral algorithms.

We first show how to reduce the question of finding a good balanced
cut to simulating logarithmic number of continuous-time random walks,
using techniques from semidefinite programming, and matrix exponential
updates.

Next, we show how to approximately simulate the required random walks
in near-linear time. The natural approach of using a polynomial
approximation does not suffice. We show how to achieve such an
approximation using rational functions, techniques from numerical
linear algebra, and the celebrated result of Spielman and Teng on
solving linear systems.

This is joint work with Lorenzo Orecchia and Nisheeth K. Vishnoi.