Sparsest Cut on quotients of the hypercube

Alexandra Kolla, James R. Lee

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We present a simple construction and analysis of an Ω(log logN) 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 logN), and why new ideas are needed in order to derive stronger examples.

Original languageEnglish (US)
Title of host publicationTheory of Computing 2011 - Proceedings of the 17th Computing
Subtitle of host publicationThe Australasian Theory Symposium, CATS 2011
Number of pages11
StatePublished - 2011
Externally publishedYes
EventTheory of Computing 2011 - 17th Computing: The Australasian Theory Symposium, CATS 2011 - Perth, WA, Australia
Duration: Jan 17 2011Jan 20 2011

Publication series

NameConferences in Research and Practice in Information Technology Series
ISSN (Print)1445-1336


OtherTheory of Computing 2011 - 17th Computing: The Australasian Theory Symposium, CATS 2011
CityPerth, WA


  • Integrality gap
  • Semidefinite programming
  • Sparsest Cut

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications
  • Hardware and Architecture
  • Information Systems
  • Software


Dive into the research topics of 'Sparsest Cut on quotients of the hypercube'. Together they form a unique fingerprint.

Cite this