An information complexity approach to extended formulations

Mark Braverman, Ankur Moitra

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

57 Scopus citations


We prove an unconditional lower bound that any linear pro- gram that achieves an O(n1-ε) approximation for clique has size 2 Ω(n-ε). There has been considerable recent interest in proving unconditional lower bounds against any linear pro- gram. Fiorini et al. [13] proved that there is no polyno- mial sized linear program for traveling salesman. Braun et al. [7] proved that there is no polynomial sized O(n 1/2-ε)- approximate linear program for clique. Here we prove an optimal and unconditional lower bound against linear pro- grams for clique that matches Håstad's [15] celebrated hard- ness result. Interestingly, the techniques used to prove such lower bounds have closely followed the progression of tech- niques used in communication complexity. Here we develop an information theoretic framework to approach these ques- tions, and we use it to prove our main result. Also we resolve a related question: How many bits of communication are needed to get ε-advantage over random guessing for disjointness? Kalyanasundaram and Schnitger [18] proved that a protocol that gets constant advantage re- quires (n) bits of communication. This result in conjunc- tion with amplification implies that any protocol that gets ε-advantage requires Ω(ε2n) bits of communication. Here we improve this bound to Ω (εn), which is optimal for any > 0.

Original languageEnglish (US)
Title of host publicationSTOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing
Number of pages10
StatePublished - 2013
Event45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States
Duration: Jun 1 2013Jun 4 2013

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Other45th Annual ACM Symposium on Theory of Computing, STOC 2013
Country/TerritoryUnited States
CityPalo Alto, CA

All Science Journal Classification (ASJC) codes

  • Software


  • Communication complexity
  • Extended formulations
  • Nonnegative rank


Dive into the research topics of 'An information complexity approach to extended formulations'. Together they form a unique fingerprint.

Cite this