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 |
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.