Authors: Alexander E. Black, Christoph Hertrich, Stefan Kober, Georg Loho
Organizations: Department of Mathematics, Bowdoin College · Department Liberal Arts and Social Sciences, University of Technology Nuremberg · Department of Mathematics, London School of Economics and Political Science · Institute of Mathematics, Freie Universität Berlin
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.
Figures & tables
Figure 1. Geometric interpretation of the formula in Proposition 3.4 . A feasible vector u yields q(u):=CQu+cQ∈Q . The dual certificate t , together with the normal d , certifies a valid halfspace for R that is violated by x+q(u) . Hence x∈/P .
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
We prove that there exist uniform (+,×,/)-circuits of size O(n3) to compute the basis generating polynomial of regular matroids on n elements. By tropicalization, this implies that there exist uniform (max,+,−)-circuits and ReLU neural networks of the same size for weighted basis maximization of regular matroids. As a consequence in linear programming theory, we obtain a first example where taking the difference of two extended formulations can be more efficient than the best known individual extended formulation for the base polytope of regular matroids of size O(n6) by Aprile and Fiorini. Such differences have recently been introduced as virtual extended formulations. The proof of our main result relies on a fine-tuned version of Seymour's decomposition of regular matroids which allows us to identify and maintain graphic substructures to which we can apply a local version of the star-mesh transformation.
Christoph Hertrich, Stefan Kober, Georg Loho
University of Technology Nuremberg, Germany · Universit´e Libre de Bruxelles, Belgium · Freie Universität Berlin, Germany +1
For compact convex sets L,K⊂Rn, denote by λK(L) the smallest size of a homothet of K that contains L. We define a measure of symmetry based on the n-simplex Δ=Δn⊂Rn as the ratio
ρΔ(L):=λΔ(L)λ−Δ(L).
We study this measure and deduce the following results: (1) The classical Minkowski measure of symmetry m∗(L) can be defined as an affine-invariant version of ρΔ(L). (2) We improve the stability analysis for the Minkowski measure of symmetry; if m∗(L)≥n−ε then L is 1−ε1-close to Δ in the Banach--Mazur distance. (3) We obtain a novel characterization of simplices as the only convex bodies K for which the function L↦λK(L) is additive (a property we term ``outer additivity''). (4) Motivated by the expressivity of ReLU neural networks, we study the depth complexity of polytopes in Rn under the two operations: Minkowski sum and convex hull of a union. We prove the sharp bound ρΔ(P)≤2d−1 for every polytope P of depth complexity d. In other words, simplices cannot be approximated by low-depth polytopes.
We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratic polynomials. This holds even when the polynomials are multilinear, each variable appears in at most three monomials, and the approximation factor is inverse polynomial. As a direct consequence, we obtain the first PPAD-hardness results for two-team zero-sum polymatrix games.
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
Bocconi University · Politecnico di Milano · University of Oxford