11 papers
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…
Short circuit walks in fixed dimension
Alexander E. Black, Christian Nöbel, Raphael Steiner
Circuit augmentation schemes are a family of combinatorial algorithms for linear programming that generalize the simplex method. To solve the linear program, they construct a so-ca…
Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Eleon Bach, Alexander E. Black, Sophie Huiberts +1
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. To further progress our understanding of how algorithms work in practice,…
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…
Exponential Lower Bounds for Many Pivot Rules for the Simplex Method
Alexander E. Black
The existence of a pivot rule for the simplex method that guarantees a strongly polynomial run-time is a longstanding, fundamental open problem in the theory of linear programming.…