The Weizmann Institute of Science
Faculty of Mathematics and Computer Science
Walmart Lecture Series in Cryptography and Complexity
Lecture Hall, Room 1, Ziskind Building
on Wednesday, May 4, 2011
at 11:00
NOTE UNUSUAL TIME
Nisheeth Vishnoi
Microsoft Research India
will speak on
Fast Spectral Algorithms for Graph Partitioning
and Graph Decomposition
Abstract:
The main object of this talk is a graph decomposition that partitions a graph
in a number of internally-well connected pieces (almost expanders) while
ensuring that only a small number of edges connect different pieces. These
decomposition arise in fundamental algorithmic problems, including graph
sparsification, clustering and the solution of certain systems of linear
equations.
This talk will focus on how to produce such a decomposition very fast, i.e. in
nearly-linear time, using a novel semidefinite programming approach.
This is joint work with Lorenzo Orecchia.