Two Linear Programs are Better than One

arXiv:2610.15909v1 Announce Type: cross Abstract: The extension complexity operatorname{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 operatorname{vxc}(P) of a polytope P, which is the minimum of operatorname{xc}(Q) + operatorname{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 Hrubes that extends the counting arguments of Rothvoss. Finally, we show that the maximum virtual extension complexity of a polygon with n vertices is Theta(sqrt{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.

Source: arXiv cs.LG | 2026-10-14