Spectral Redemption

Tuesday, May 19, 2015 - 3:30pm - 4:20pm
Keller 3-180
Lenka Zdeborova (Centre National de la Recherche Scientifique (CNRS))
This talk will be about the non-backtracking matrix of a graph. I will review recent works on its spectral properties for random graphs and concentrate on its algorithmic applications. Notably I will talk about optimality of the corresponding spectral algorithm for clustering of sparse networks and for analysis of percolation on sparse networks. The relation with linearized belief propagation for the corresponding graphical model will be instrumental.
MSC Code: