Sparsest Cut on Quotients of the Hypercube

Kolla, A. and Lee, J.

    We present a simple construction and analysis of an Ω(log log N ) integrality gap for the well-known Sparsest Cut semi-definite program (SDP). This holds for the uniform demands version (i.e. edge expansion). The same quantitative gap was proved earlier by Devanur, Khot, Saket, and Vishnoi [STOC 2006], following an integrality gap for non-uniform demands due to Khot and Vishnoi [FOCS 2005]. These previous constructions involve a complicated SDP solution and analysis, while our gap instance, vector solution, and analysis are somewhat simpler and more intuitive. Furthermore, our approach is rather general, and provides a variety of different gap examples derived from quotients of the hypercube. It also illustrates why the lower bound is stuck at Ω(log log N ), and why new ideas are needed in order to derive stronger examples.
Cite as: Kolla, A. and Lee, J. (2011). Sparsest Cut on Quotients of the Hypercube. In Proc. Computing: The Australasian Theory Symposium (CATS 2011) Perth, Australia. CRPIT, 119. Alex Potanin and Taso Viglas Eds., ACS. 11-22
pdf (from pdf (local if available) BibTeX EndNote GS