Abstract:
Recently, there has been growing interest in graph sparsification --- replacing dense/large graphs with sparser/smaller graphs while (approximately) preserving the value of certain graph parameters. This includes spanners/emulators (where pair-wise distances between vertices are preserved), vertex sparsifiers (where the connectivity of terminal subsets are preserved), cut sparsifiers (where the weights of all cuts are preserved), spectral sparsifiers (where quadratic forms defined on the graph Laplacian are preserved), etc. I will briefly survey these various graph sparsfication paradigms highlighting some of the key results and future challenges in each area. Then, I will focus on cut sparsification and describe a general framework for constructing cut sparsifiers in undirected graphs, and use it to simplify, unify and improve upon previous combinatorial and algorithmic results in this area.

Biography:
Debmalya Panigrahi is currently a postdoctoral researcher in the theory group at Microsoft Research, Redmond and is going to join Duke University as an Assistant Professor of Computer Science in July 2013. His research interests are in theoretical computer science, specifically in algorithms for combinatorial optimization, and in applied algorithms. He obtained his PhD from MIT in 2012, where he was a recipient of the MIT Presidential Fellowship.