Polytopes with Bounded Integral Slack Matrices Have Sub-Exponential Extension Complexity
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916168887959552 |
|---|---|
| author | Dong, Sally Rothvoss, Thomas |
| author_facet | Dong, Sally Rothvoss, Thomas |
| contents | We show that any bounded integral function $f : A \times B \mapsto \{0,1, \dots, Δ\}$ with rank $r$ has deterministic communication complexity $Δ^{O(Δ)} \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,Δ\}$ has extension complexity at most $\exp(Δ^{O(Δ)} \cdot \sqrt{n} \cdot \log n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_16159 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Polytopes with Bounded Integral Slack Matrices Have Sub-Exponential Extension Complexity Dong, Sally Rothvoss, Thomas Discrete Mathematics Combinatorics We show that any bounded integral function $f : A \times B \mapsto \{0,1, \dots, Δ\}$ with rank $r$ has deterministic communication complexity $Δ^{O(Δ)} \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,Δ\}$ has extension complexity at most $\exp(Δ^{O(Δ)} \cdot \sqrt{n} \cdot \log n)$. |
| title | Polytopes with Bounded Integral Slack Matrices Have Sub-Exponential Extension Complexity |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2307.16159 |