Polytopes with Bounded Integral Slack Matrices Have Sub-Exponential Extension Complexity

We show that any bounded integral function $f:A\times B\mapsto \{0,1,\dots ,\mathrm{\Delta }\}$ with rank $r$ has deterministic communication complexity ${\mathrm{\Delta }}^{O(\mathrm{\Delta })}\cdot \sqrt{r}\cdot \log r$, where the rank of $f$ is defined to be the rank of the $A\times B$ matrix whose entries are the function values. As a corollary, we show that any $n$-dimensional polytope that admits a slack matrix with entries from $\{0,1,\dots ,\mathrm{\Delta }\}$ has extension complexity at most $\exp ({\mathrm{\Delta }}^{O(\mathrm{\Delta })}\cdot \sqrt{n}\cdot \log n)$.