6 papers · 1 filter
Two Linear Programs are Better than One
Alexander E. Black, Christoph Hertrich, Stefan Kober +1
The extension complexity of a polytope is the minimum number of facets of a polytope that projects onto it. Motivated by the complexity of neural network…
Monotone Diameters of Lattice Polytopes
Alexander E. Black
An influential 1989 result of Naddef shows that the diameters of -polytopes are at most their dimension. This was extended shortly after by Kleinschmidt and Onn to any lattice…
Any Proof of Polynomial Hirsch Must be Completely Incoherent
Alexander E. Black, Lei Xue
In 1992, Billera and Sturmfels introduced coherent monotone paths on polytopes as part of their description of the fiber polytope construction, and later in 1994 showed with Kapran…
Saturation for Non-Symmetric Macdonald Polynomials
Milo Bechtloff Weising, Alexander E. Black
We prove that supports of non-symmetric Macdonald polynomials are -convex. As a consequence, we resolve a 2019 conjecture of Monical, Tokcan, and Yong that they have the saturat…
Random Shadows of Fixed Polytopes
Alexander E. Black, Francisco Criado
Estimating the number of vertices of a two dimensional projection, called a shadow, of a polytope is a fundamental tool for understanding the performance of the shadow simplex meth…
From linear programming to colliding particles
Alexander E. Black, Niklas Lütjeharms, Raman Sanyal
Although simplices are trivial from a linear optimization standpoint, the simplex algorithm can exhibit quite complex behavior. In this paper we study the behavior of max-slope piv…