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

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