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

Abstract

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 exists an $A\subseteq \{0,1{\}}^n$ such that the extension complexity of any $P$ with $P\cap \{0,1{\}}^n=A$ must be at least $2^{\frac{n}{3}(1-o(1))}$. We also remark that the extension complexity of any 0/1-polytope in ${\mathbb{R}}^n$ is at most $O(2^n/n)$ and pose the problem whether the upper bound can be improved to $O(2^{cn})$, for $c<1$.