From the 1 of 6 linked papers with an AI index.
6 papers
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
The paper constructs families of polytopes for which every coherent monotone path induced by a linear function has exponential length, disproving a polynomial‑Hirsch‑type conjectur…
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,…
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…
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…
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…