Large 00004

Solve, Walk, Cut

Nisheeth Vishnoi

Recorded 20 June 2012 in Lausanne, Vaud, Switzerland

Event: SuRI - I&C - Summer Research Institute

Abstract

In this talk I will address the following question:

Can one speed-up simulation of random walks given the ability to solve a system of linear equations quickly?

Computing probability distributions that arise from random walks on undirected graphs quickly is a primitive useful in many combinatorial and algorithmic settings and, more recently, have been used in solving certain convex programs combinatorially.

The answer to the above question will be revealed via an intricate story which stitches together methods from spectral graph theory, numerical linear algebra and approximation theory.

As an application, I will highlight a joint work with L. Orecchia and S. Sachdeva, which is the first near-linear time approximation algorithm, that achieves the Cheeger bound, to cut a graph into two roughly equal parts while minimizing the conductance of the partition.

Watched 8986 times.

 Watch