Extension Complexity of the Correlation Polytope

Pierre Aboulker, Samuel Fiorini, Tony Huynh +2

We prove that for every $n$-vertex graph $G$, the extension complexity of the correlation polytope of $G$ is $2^{O(\mathrm{tw}(G)+\log n)}$, where $\mathrm{tw}(G)$ is the treewid…