DIMACS Theoretical Computer Science Seminar

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


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