Skip to main content.
Advanced search >
<< Back to previous page Print

<< Thursday, October 19, 2017 >>


Remind me

Tell a friend

Add to my Google calendar (bCal)

Download to my calendar

Bookmark and ShareShare


GraphXD Seminar: Spectral Sparsification of Graphs

Seminar | October 19 | 5:30-7 p.m. | 1011 Evans Hall


Nikhil Srivastava, Dept. of Mathematics, UC Berkeley

Berkeley Institute for Data Science


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 Laplacians of H and G are close, so that H captures the spectral behavior of G while being much cheaper to store and perform computations on. We survey a line of work showing that spectral sparsifiers with constant degree exist for every graph and can be computed efficiently.


bids@berkeley.edu, 510-664-4506