5 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…
Enumerating iterated tilted algebras in type
Alexander E. Black, Jonathan E. Gordon, Ray Maresca
We show that isoclasses of iterated tilted algebras in type are in bijection with non-crossing spanning trees up to rotation on a convex n+1-gon. This is done by constructing…
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…
Finding Short Paths on Simple Polytopes
Alexander E. Black, Raphael Steiner
We prove that computing a shortest monotone path to the optimum of a linear program over a simple polytope is NP-hard, thus resolving a 2022 open question of De Loera, Kafer, and S…