Abstract
Given a graph , let L be its associated normalized Laplacian matrix and let be the smallest eigenvalue of L. The fundamental Cheeger's Inequality states that is a quantitative measure of the disconnectivity of the graph, which also provides a theoretical analysis of Fiedler's spectral algorithm for finding a sparse cut. Trevisan proved a variant of Cheeger's Inequality for , which shows a connection between and the bipartiteness of the graph.
In this talk I will show how to generalize these results further to digraphs, by looking at a class of rotated Laplacian matrices. I will show that its first eigenvalue characterizes the periodicity of the digraph. This provides a unified way to look at these variants of Cheeger's Inequality. In the second part of the talk, I will explain how to apply these observations to design and analyze new spectral algorithms for finding many periodic components, using higher eigenvalues of the rotate Laplacians. This also implies a new higher-order Cheeger-type inequality for periodicity.
Time
Tuesday, Apr.28, 10:00--11:00
Speaker
Jiyu Zhang is a PhD student at Bocconi University in Milan, Italy. He was advised by Luca Trevisan, later co-advised by Salil Vadhan and Alon Rosen. He is broadly interested in algorithms, computational complexity theory, and their interplay with related areas of mathematics.
Room
Room 104
