Two Linear Programs are Better than One

@misc{black2026linear,
  title = {{Two Linear Programs are Better than One}},
  author = {Alexander E. Black and Christoph Hertrich and Stefan Kober and Georg Loho},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.15909},
  eprint = {2610.15909},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.15909},
}

TY  - UNPB
TI  - Two Linear Programs are Better than One
AU  - Alexander E. Black
AU  - Christoph Hertrich
AU  - Stefan Kober
AU  - Georg Loho
PY  - 2026
DA  - 2026/10/11
PB  - arXiv
DO  - 10.48550/arxiv.2610.15909
UR  - https://arxiv.org/abs/2610.15909
AB  - The extension complexity xc(P) of a polytope P is the minimum number of facets of a polytope that projects onto it. Motivated by the complexity of neural networks, Hertrich and Loho introduced the virtual extension complexity vxc(P) of a polytope P, which is the minimum of xc(Q) + xc(R) among all polytopes Q and R such that P+Q=R. We show the following results pertaining to virtual extension complexity. First, we resolve the core open problem on the topic by showing the virtual extension complexity can be exponentially smaller than extension complexity. Second, we show there are matroid base polytopes with exponential virtual extension complexity by adapting a semi-algebraic counting argument by Hrubeš that extends the counting arguments of Rothvoss. Finally, we show that the maximum virtual extension complexity of a polygon with n vertices is Θ(√n). This resolves an analogue of a question on extension complexity of Fiorini, Rothvoss, and Tiwary in 2011 in the case of virtual extension complexity.
ER  -