Abstract
Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a single matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms have been quite successful for graph partitioning problems among other applications. In this talk, I will present a scenario for graph partitioning with censored edges where spectral algorithms with a single encoding matrix is suboptimal. However, if we use multiple encoding matrices instead of one, that achieves optimality and leads to a much powerful and flexible class of algorithms. This is joint work with Julia Gaudio, Elchanan Mossel, Colin Sandon