I will first give an overview of several constructions of graph sparsifiers and their properties. I will then present a method of sparsifying a subgraph W of a graph G with optimal number of edges and talk about the implications of subgraph sparsification in constructing nearly-optimal ultrasparsifiers and optimizing the algebraic connectivity of a graph by adding few edges.

The talk is based on joint work with Makarychev,Saberi,Teng.

Watch Online
Hi-Res	603.11 MB
Lo-Res	335.34 MB