ECCC-Report TR12-131https://eccc.weizmann.ac.il/report/2012/131Comments and Revisions published for TR12-131en-usThu, 13 Feb 2014 17:25:58 +0200
Revision 1
| An Information Complexity Approach to Extended Formulations |
Mark Braverman,
Ankur Moitra
https://eccc.weizmann.ac.il/report/2012/131#revision1We prove an unconditional lower bound that any extended formulation that achieves an $O(n^{1-\epsilon})$ approximation for clique has size $2^{\Omega(n^\epsilon)}$. There has been considerable recent interest in proving lower bounds for extended formulations. Fiorini et al proved that there is no polynomial sized extended formulation for traveling salesman. Braun et al proved that there is no polynomial sized $O(n^{1/2 - \epsilon})$-approximate extended formulation for clique. Here we prove an optimal and unconditional lower bound against extended formulations for clique that matches H{\aa}stad'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 $\epsilon$-advantage over random guessing for disjointness? Kalyanasundaram and Schnitger proved that a protocol that gets constant advantage requires $\Omega(n)$ bits of communication. This result in conjunction with amplification implies that any protocol that gets $\epsilon$-advantage requires $\Omega(\epsilon^2 n)$ bits of communication. Here we improve this bound to $\Omega(\epsilon n)$, which is optimal for any $\epsilon > 0$. Thu, 13 Feb 2014 17:25:58 +0200https://eccc.weizmann.ac.il/report/2012/131#revision1
Paper TR12-131
| An Information Complexity Approach to Extended Formulations |
Mark Braverman,
Ankur Moitra
https://eccc.weizmann.ac.il/report/2012/131We prove an unconditional lower bound that any linear program that achieves an $O(n^{1-\epsilon})$ approximation for clique has size $2^{\Omega(n^\epsilon)}$. 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(n^{1/2 - \epsilon})$-approximate linear program for clique. Here we prove an optimal and unconditional lower bound against linear programs for clique that matches H{\aa}stad'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 $\epsilon$-advantage over random guessing for disjointness? Kalyanasundaram and Schnitger proved that a protocol that gets constant advantage requires $\Omega(n)$ bits of communication. This result in conjunction with amplification implies that any protocol that gets $\epsilon$-advantage requires $\Omega(\epsilon^2 n)$ bits of communication. Here we improve this bound to $\Omega(\epsilon n)$, which is optimal for any $\epsilon > 0$. Thu, 18 Oct 2012 03:18:22 +0200https://eccc.weizmann.ac.il/report/2012/131