The Extension Complexity of Polytopes with Bounded Integral Slack Matrices

We show that any bounded integral function \(f: A \times B \mapsto \{0,1, \dots , \varDelta \}\) with rank r has deterministic communication complexity \(\varDelta ^{O(\varDelta )} \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 ,\varDelta \}\) has extension complexity at most \(\textrm{exp}(\varDelta ^{O(\varDelta )} \cdot \sqrt{n} \cdot \log n)\) .