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

Sally Dong, Thomas Rothvoss

We show that any bounded integral function $f:A\times B\mapsto \{0,1,\dots ,\Delta \}$ with rank $r$ has deterministic communication complexity $Δ^{O(Δ)} \cdot \sqrt{r} \cdot \log r…