Skip to main content

An information complexity approach to extended formulations

Author(s): Braverman, Mark; Moitra, Ankur

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1qc1j
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorMoitra, Ankur-
dc.date.accessioned2021-10-08T19:45:00Z-
dc.date.available2021-10-08T19:45:00Z-
dc.date.issued2013-06en_US
dc.identifier.citationBraverman, Mark, and Ankur Moitra. "An information complexity approach to extended formulations." In Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (2013): 161-170. doi:10.1145/2488608.2488629en_US
dc.identifier.urihttps://eccc.weizmann.ac.il/report/2012/131/-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1qc1j-
dc.description.abstractWe prove an unconditional lower bound that any linear program 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 program. Fiorini et al. proved that there is no polynomial sized linear program for traveling salesman. Braun et al. proved that there is no polynomial sized O(n1/2 - ε)-approximate linear program for clique. Here we prove an optimal and unconditional lower bound against linear programs for clique that matches Hastad's celebrated hardness result. Interestingly, the techniques used to prove such lower bounds have closely followed the progression of techniques used in communication complexity. Here we develop an information theoretic framework to approach these questions, 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 proved that a protocol that gets constant advantage requires Ω(n) bits of communication. This result in conjunction with amplification implies that any protocol that gets ε-advantage requires Ω(ε2 n) bits of communication. Here we improve this bound to Ω(ε n), which is optimal for any ε > 0.en_US
dc.format.extent161 - 170en_US
dc.language.isoen_USen_US
dc.relation.ispartofProceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computingen_US
dc.relation.ispartofseriesSTOC '13;-
dc.rightsAuthor's manuscripten_US
dc.titleAn information complexity approach to extended formulationsen_US
dc.typeConference Articleen_US
dc.identifier.doi10.1145/2488608.2488629-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
InformationComplexityApproachExtendedFormulations.pdf610.97 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.