An information complexity approach to extended formulations

We prove an unconditional lower bound that any linear pro- gram that achieves an O(n^1-ε) 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 Ω(ε²n) bits of communication. Here we improve this bound to Ω (εn), which is optimal for any > 0.