Two Linear Programs are Better than One

The extension complexity operatornamexc(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 operatornamevxc(P) of a polytope P, which is the minimum of operatornamexc(Q) + operatornamexc(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 Hrubevs that extends the counting arguments of Rothvoss. Finally, we show that the maximum virtual extension complexity of a polygon with n vertices is Theta(√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.