DIMACS Theoretical Computer Science Seminar

Title: Towards a better approximation for Sparsest Cut?

Speaker: Ali Kemal Sinop, Princeton University

Date: Wednesday, May 1, 2013 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


We give a new $(1+eps)$-approximation for sparsest cut problem on graphs where small sets expand significantly more than the sparsest cut (sets of size $n=r$ expand by a factor $\sqrt{log n log r}$ bigger, for some small $r$; this condition holds for many natural graph families). We give two diff?erent algorithms. One involves Guruswami-Sinop rounding on the level-r Lasserre relaxation. The other is combinatorial and involves a new notion called Small Set Expander Flows (inspired by the expander flows of [ARV09]) which we show exists in the input graph. Both algorithms run in time $2^{O(r)} poly(n)$.

We also show similar approximation algorithms in graphs with genus $g$ with an analogous local expansion condition.

This is the first algorithm we know of that achieves $(1+\eps)$-approximation on such general family of graphs.

Joint work with Sanjeev Arora and Rong Ge.

See: http://paul.rutgers.edu/~yixinxu/theory-spring13.html