Geometry and Expansion: A Survey of Recent Results

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.

Speaker's Bio: Sanjeev Arora is Professor of Computer Science at Princeton University and works in computational complexity theory, approximation algorithms for NP-hard problems, geometric algorithms, and probabilistic algorithms. He has received the ACM Dissertation Prize, the SIGACT-EATCS Goedel Prize, and the Packard Fellowship.