{"id":"arxiv/2610.15909","url":"https://arxiv.org/abs/2610.15909","tags":["math.CO","cs.CC","cs.DM","cs.LG","math.OC"],"score":0,"title":"Two Linear Programs are Better than One","domain":"math.CO","source":"arxiv","authors":["Alexander E. Black","Christoph Hertrich","Stefan Kober","Georg Loho"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-11","reactions":{}}