AN INFORMATION COMPLEXITY APPROACH TO EXTENDED FORMULATIONS*

Abstract: Often it is possible to express a given polytope $P$ as the projection of a higher dimensional polytope $Q$ and in so doing to drastically reduce the number of facets needed. We call $Q$ an extended formulation for $P$. In fact, small extended formulations are known for a number of polytopes that arise in combinatorial optimization and yet there are many polytopes that we do not expect to have a small extended formulation -- e.g. polytopes that capture the solutions to hard optimization problems. Can we prove unconditional results that these polytopes do not have small extended formulations?
Recently, there has been a revival of interest in this question. A breakthrough result of Fiorini et al (STOC 2012) established that the TSP polytope has no subexponential sized extended formulation. Subsequently Braun et al (FOCS 2012) proved that the clique polytope has no subexponential $O(n^{1/2 - \epsilon})$-approximate extended formulation either. Here we give a new approach to these lower bounds based on information complexity --roughly a too-goodto-be-true extended formulation would allow us to sample from a distribution using too few bits of entropy, and this is the means by which we prove our lower bounds. We use this framework to prove that the clique polytope has no subexponential $O(n^{1 - \epsilon})$-approximate extended formulation, thus giving an optimal and unconditional lower bound that matches Hastad's celebrated hardness of approximation results for clique.

*This is based on joint work with Mark Braverman.