Geometry and Expansion: A Survey of Recent Results

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 l1 space embeds in l2 with distortion close to O(√{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 Details

Sanjeev Arora received his PhD from UC Berkeley in 1994, and since then has been a faculty member at the Computer Science department at Princeton University. His research interests include complexity theory (especially probabilistically checkable proofs), computing approximate solutions to NP-hard problems, and geometric embeddings of finite metric spaces.

Date:
Speakers:
Sanjeev Arora
Affiliation:
Princeton University

    • Portrait of Jeff Running

      Jeff Running