Abstract:

Partitioning a graph into two (or more) large pieces while minimizing the size of the “interface” between them is a fundamental combinatorial problem.Graph partitions or separators are central objects of study in the theory of Markov chains, geometric embeddings and are a natural algorithmic primitive in numerous settings, including clustering, divide and conquer approaches, PRAM emulation, VLSI layout, and packet routing in distributed networks.

This talk surveys a new geometric view of expansion that has led to new results in computer science and mathematics. It originated in some joint work with Satish Rao and Umesh Vazirani and has motivated several other papers. It has led to better approximation algorithms for a host of NP-hard combinatorial problems (including SPARSEST CUT, MIN-2-CNF DELETION, MIN-LINEAR ARRANGEMENT). It has also led to better geometric embeddings for metric spaces, including a proof that every n-point l_1 space embeds in l_2 with distortion close to O(\sqrt{log n}), improving upon the trivial O(log n) bound from Bourgain's theorem.

Other applications include a better structural understanding of graph expansion, as well as faster algorithms for approximating expansion.

(Based upon several papers, including those not by me.)

Short Bio:

Sanjeev Arora (born January 1968) is a computer scientist who is best known for his seminal work on probabilistically checkable proofs and, in particular, on the PCP theorem. He is also known for his work on designing new approximation algorithms for Geometric Traveling Salesman problem and graph partitioning problems. His PhD thesis on probabilistically checkable proofs received the ACM Doctoral Dissertation Award in 1995. He was awarded the Gdel Prize for his work on the PCP theorem in 2001, and in 2009 he was inducted as a Fellow of the Association for Computing Machinery.

His research area is theoretical computer science, specifically in computational complexity theory, uses of randomness in computation, probabilistically checkable proofs, computing approximate solutions to NP-hard problems, and geometric embeddings of metric spaces.