On the extension complexity of polytopes separating subsets of the Boolean cube

Pavel Hrubeš, Navid Talebanfard

We show that 1. for every $A\subseteq \{0,1{\}}^n$, there exists a polytope $P\subseteq {\mathbb{R}}^n$ with $P\cap \{0,1{\}}^n=A$ and extension complexity $O(2^{n/2})$, 2. there ex…