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.