Title: Subgraph Sparsification and Nearly Optimal Ultrasparsifiers
Speaker: Alexandra Kolla, Microsoft Research
Date: Wednesday, September 29, 2010 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In this talk, we present new (spectral) techniques for approximating a large graph with a smaller one. Namely, we show how, given a large graph G and a subgraph H of it, we can choose a very small number of edges H' out of H such that replacing H with H' does not change the spectrum of G by much. We discuss significant implications of our techniques in two interesting practical problems: creating cost-efficient, well-connected networks and speeding up linear system solvers.
Joint work with Yury Makarychev, Amin Saberi, Shanghua Tengi