Graph and Subgraph Sparsification and its Implications to Linear System Solving and Transforming Graphs into Expanders

Video of this lecture

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Graph and Subgraph Sparsification and its Implications to Linear System Solving and Transforming Graphs into Expanders
Speaker:Alexandra Kolla
Affiliation:Member, School of Mathematics
Date:Tuesday, November 10
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/sparsification

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.