### 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

Abstract:

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