Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.11382 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910019874717696 |
|---|---|
| author | Szusterman, M. |
| author_facet | Szusterman, M. |
| contents | This paper investigates the extension complexity of polytopes by exploiting the correspondence between non-negative factorizations of slack matrices and randomized communication protocols. We introduce a geometric characterization of extension complexity based on the width of Markovian protocols, as a variant of the framework introduced by Faenza et al. This enables us to derive a new upper bound of $\tilde{O}(n^3\cdot 1.5^n)$ for the extension complexity of the matching polytope $P_{\text{match}}(n)$, improving upon the standard $2^n$-bound given by Edmonds' description. Additionally, we recover Goemans' compact formulation for the permutahedron using a one-round protocol based on sorting networks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_11382 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Markovian protocols and an upper bound on the extension complexity of the matching polytope Szusterman, M. Discrete Mathematics Data Structures and Algorithms This paper investigates the extension complexity of polytopes by exploiting the correspondence between non-negative factorizations of slack matrices and randomized communication protocols. We introduce a geometric characterization of extension complexity based on the width of Markovian protocols, as a variant of the framework introduced by Faenza et al. This enables us to derive a new upper bound of $\tilde{O}(n^3\cdot 1.5^n)$ for the extension complexity of the matching polytope $P_{\text{match}}(n)$, improving upon the standard $2^n$-bound given by Edmonds' description. Additionally, we recover Goemans' compact formulation for the permutahedron using a one-round protocol based on sorting networks. |
| title | Markovian protocols and an upper bound on the extension complexity of the matching polytope |
| topic | Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.11382 |