Ankur Moitra colloquium, Tuesday, 02/08, 3:30
David Kempe
out next theory talk - and next theory faculty candidate - is Ankur
Moitra from MIT. He has done some great work on graph sparsification
and learning mixtures of Gaussians, among others.
All the important information is below. I am looking forward to seeing
many of you at the talk.
Date: Tuesday, 02/08, 3:30pm
Location: SSL 150
Speaker: Ankur Moitra, MIT
Title: Vertex Sparsification
Abstract: Suppose we are given a gigantic communication network, but are only
interested in a small number of nodes (clients). There are many routing
problems we could be asked to solve for our clients. Is there a much smaller
network - that we could write down on a sheet of paper and put in our pocket -
that approximately preserves all the relevant communication properties of the
original network? As we will demonstrate, the answer to this question is YES,
and we call this smaller network a vertex sparsifier.
In fact, if we are asked to solve a sequence of optimization problems
characterized by cuts or flows, we can compute a good vertex sparsifier ONCE
and discard the original network. We can run our algorithms (or approximation
algorithms) on the vertex sparsifier as a proxy - and still recover
approximately optimal solutions in the original network. This novel pattern
saves both space (because the network we store is much smaller) and time
(because our algorithms run on a much smaller graph).
Additionally, we apply these ideas to obtain a master theorem for graph
partitioning problems - as long as the integrality gap of a standard linear
programming relaxation is bounded on trees, then the integrality gap is at most
a logarithmic factor larger for general networks. This result implies optimal
bounds for many well studied graph partitioning problems as a special case, and
even yields optimal bounds for more challenging problems that had not been
studied before. Morally, these results are all based on the idea that even
though the structure of optimal solutions can be quite complicated, these
solution values can be approximated by crude (even linear) functions.
Bio: Ankur Moitra is a fourth year PhD student in the theory of computation
group at MIT, advised by Tom Leighton. His main research interests are in
approximation algorithms, learning theory and applied probability. He received
a B.S. in electrical and computer engineering from Cornell in 2007, and a M.S.
in computer science from MIT in 2009. Additionally, he has spent a number of
summers working in industry, both as a quant at Citigroup and designing blog
ranking algorithms at Google.