Spectral Sparsification of Graphs
Oct 19, 2017 5:30pm to 7:00pm
1011 Evans Hall
Happening As Scheduled
Many important properties of an undirected graph manifest themselves spectrally in the eigenvalues or quadratic forms of matrices related to the graph. For instance, the connectivity structure, electrical properties, and random walk behavior of a graph are determined by its Laplacian matrix. A spectral sparsifier of a graph G is a sparse graph H on the same set of vertices such that the...
Nikhil Srivastava, Dept. of Mathematics, UC Berkeley (Speaker)