Some 0/1 polytopes need exponential size extended formulations

We prove that there are 0/1 polytopes P subset of R-n that do not admit a compact LP formulation. More precisely we show that for every n there is a set X subset of {0, 1}(n) such that conv(X) must have extension complexity at least 2(n/2.(1-o(1))). In otherwords, every polyhedron Q that can be linearly projected on conv(X) must have exponentially many facets. In fact, the same result also applies if conv(X) is restricted to be a matroid polytope. Conditioning on NP not subset of P-/poly, our result rules out the existence of a compact formulation for any NP-hard optimization problem even if the formulation may contain arbitrary real numbers.