Events Calendar

CS Colloquium

Speaker: Ankur Moitra, MIT

Talk 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.


Biography: 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.


Host: Prof. David Kempe, USC

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: Kanak Agrawal