Theory Talk

Friday, July 15, 2016 - 1:00pm to 2:00pm

Location:

7101 Gates & Hillman Centers

Speaker:

RICHARD PENG, Assistant Professor http://www.cc.gatech.edu/people/richard-peng

For More Information, Contact:

nlc@cs.cmu.edu

We show dynamic algorithms for graph sparsification problems that take polylogarithmic time per each insertion / deletion in the graph. Our three main results are as follows. First, we give a fully dynamic algorithm for maintaining an (1 \pm \epsilon)-spectral sparsifier with amortized update time poly(\log{n},\epsilon^{-1}). Second, we give a fully dynamic algorithm for maintaining an (1 \pm \epsilon)-cut sparsifier with worst-case update time poly(\log{n},\epsilon^{-1}). Third, we apply our dynamic sparsifier algorithm to obtain a fully dynamic algorithm for maintaining an (1 + \epsilon)-approximate minimum cut in an unweighted, undirected, bipartite graph with amortized update time poly(\log{n},\epsilon^{-1}). Joint work with Ittai Abraham, David Durfee, Ioannis Koutis, and Sebastian Krinninger. Copy of Manuscript — Richard Peng is an assistant professor in the School of Computer Science at the Georgia Institute of Technology. His research interests are in the design, analysis, and implementation of efficient algorithms. He is involved in the Algorithms and Randomness Center and the Algorithms, Combinatorics, and Optimization program. Prior to coming to Georgia Tech, he received his PhD in Computer Science at CMU, and was an Instructor in Applied Mathematics at MIT for two years. His thesis, Algorithm Design Using Spectral Graph Theory, won the 2012/2013 CMU SCS Dissertation Award.

Keywords:

Seminar Series