PhD Seminar • Algorithms and Complexity • Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues
Please note: This PhD seminar will take place in DC 2310.
Kam Chuen (Alex) Tung, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Lap Chi Lau
The classical Cheeger’s inequality relates the edge conductance of a graph and the second smallest eigenvalue of the Laplacian matrix. Recently, Olesker-Taylor and Zanetti discovered a Cheeger-type inequality connecting the vertex expansion of a graph and the maximum reweighted second smallest eigenvalue of the Laplacian matrix.