SPECIAL TIME: 1:30 -- 2:20 pm,  Tuesday, Jan 13, 2009

PLACE: CSE 503  

SPEAKER: Reid Andersen
         Microsoft

TITLE: Finding Sparse Cuts Locally using Evolving Sets


ABSTRACT: 
A local graph partitioning algorithm finds a set of vertices with
small conductance (i.e. a sparse cut) by adaptively exploring part of a
large graph G, starting from a specified vertex.  For the algorithm to be
local, its complexity must be bounded in terms of the size of the set that
it outputs, with at most a weak dependence on the number n of vertices in G.
Previous local partitioning algorithms find sparse cuts using random
walks and personalized PageRank.  We introduce a randomized
local partitioning algorithm that finds a sparse cut by simulating the
volume-biased evolving set process, which is a Markov chain on sets of
vertices.  We prove that for any set of vertices A that has conductance at
most phi, for at least half of the starting vertices in A our algorithm
will output (with probability at least half), a set of conductance
O(phi^{1/2} log^{1/2} n).  We prove that for a given run of the
algorithm, the expected ratio between its computational complexity and the
volume of the set that it outputs is O(phi^{-1/2} polylog(n)).  In
comparison, the best previous local partitioning algorithm, due to Andersen,
Chung, and Lang, has the same approximation guarantee, but a larger ratio of
O(phi^{-1} polylog(n)) between the complexity and output volume.

Joint work with Yuval Peres.