Robust exponential lower bounds for shadow-vertex and steepest-edge simplex pivot rules: all shadow paths on cubes, every projection, and every norm

The shadow-vertex (shadow simplex) pivot rule and the steepest-edge rule are the two theoretically central families of simplex-method pivot rules and the main candidates for a provably polynomial-time simplex variant. Black (2026) constructed linear programs on which every choice of shadow projection yields an exponentially long simplex path, and combinatorial cubes on which the steepest-edge rule with any fixed norm - or simultaneously with every regular norm - visits all vertices. The paper explicitly lists the open problems its constructions leave unresolved. One of them - the existence of polytopes on which every coherent monotone path from the objective's minimum to its maximum is long - has since been resolved affirmatively by Black and Xue (2026), who exhibit, for each $d\ge 3$, a polytope on which every coherent monotone path has length at least $2^{d-1}-1$, refuting the coherent analogue of the polynomial Hirsch conjecture. The surviving open core asks for the remaining robustness upgrades: (i) combinatorial cubes on which every shadow path between a fixed pair of vertices is superpolynomial in the dimension; (ii) polytopes whose every two-dimensional projection (every shadow) has exponentially many vertices; (iii) linear programs on which the steepest-edge path is exponential for every norm simultaneously, including all norms $\eta(x)=\|Ax\|_2$ with $A$ invertible. Each question demands a worst-case family that defeats an entire parameterized family of pivot choices at once, or a proof that no such family exists.

Background

A linear program (LP) maximizes a linear objective $c^\top x$ over a polytope $P=\{x\in\mathbb{R}^n:Ax\le b\}$, a bounded intersection of finitely many halfspaces. The simplex method solves it by walking along edges of $P$ from vertex to vertex so that the objective increases at every step; such a walk is a monotone path, and a pivot rule is a rule for choosing which improving neighbor to move to. Whether any pivot rule guarantees a polynomial number of steps is a longstanding open problem in optimization, closely tied to the polynomial Hirsch conjecture, which asks whether the diameter of the graph of a polytope is bounded by a polynomial in its dimension and number of facets and remains open. The classical exponential worst-case examples, the distorted hypercubes known as Klee-Minty cubes on which Dantzig's original rule (move to the neighbor with largest objective coefficient) visits all $2^n$ vertices, and their later variants, each defeat one specific rule.

The shadow-vertex (shadow simplex) rule works as follows. The normal cone of a vertex $v$ is the set of linear objectives maximized at $v$; for a simple polytope (one where exactly $n$ facets meet at each vertex) it is a full-dimensional simplicial cone. Starting at a vertex $v$, the rule picks an auxiliary objective $w$ in the interior of the normal cone of $v$, projects $P$ onto the two-dimensional plane spanned by $w$ and $c$, and follows the boundary chain of the resulting polygon - the shadow - from the image of $v$ to the image of the $c$-optimum, lifting the chain back to a path on $P$ (a shadow path). Equivalently, a shadow path is a coherent monotone path in the sense of the fiber polytope theory of Billera and Sturmfels: a monotone path realized as the sequence of optimal solutions of the parametric program $\max (w+\lambda c)^\top x$ as $\lambda$ grows. The strongest positive results for the simplex method - expected-polynomial behavior on random LPs established in the 1970s-80s, and smoothed analysis, which measures expected running time on inputs perturbed by small random noise, introduced by Spielman and Teng and recently optimized by Bach and Huiberts - all analyze shadow-vertex variants.

The steepest-edge rule, the practical pivot rule of choice, at a current vertex $v^i$ moves to the $c$-improving neighbor $u$ maximizing the normalized improvement $c^\top(u-v^i)/\eta(u-v^i)$, where $\eta$ is a normalization function, classically the Euclidean length of the edge; Goldfarb and Sit constructed exponential examples for the 2-norm steepest-edge rule in 1979. Before Black (2026), all exponential lower bounds for both families were fragile in a precise way: for shadows, each construction exhibited one bad projection, while the method leaves the practitioner free to choose any admissible $w$; for steepest edge, only the Euclidean norm was covered.

Black (2026) removed both fragilities in one direction. A combinatorial cube is a polytope whose face lattice - the poset of its faces ordered by inclusion - is isomorphic to that of $[0,1]^n$. First, for every $n$ there is a simple $n$-polytope with $3n$ facets (with facet data of polynomial encoding length in the journal version) with a start vertex $v$ and objective $c$ such that every shadow path on it starting at $v$ has length at least $2^n$: no shadow-selecting simplex variant is weakly polynomial. Second, for every $n$ there is a simple $n$-polytope with $4n$ facets and a vertex pair $u,v$ such that every coherent path from $u$ to $v$ is exponential, so the polynomial Hirsch conjecture is false if only coherent monotone paths are allowed. Third, for any fixed norm $\eta$ (indeed any continuous positively homogeneous normalization, i.e. $\eta(\lambda x)=|\lambda|\eta(x)$), there is a combinatorial cube on which the $\eta$-steepest-edge rule visits all $2^n$ vertices; and one cube does so simultaneously for every regular norm, meaning $\eta(e_i)=1$ for every standard basis vector $e_i$, hence in particular for all $p$-norms.

The paper's own open problems delimit exactly what these constructions do not achieve: the cube question (can all shadow paths between a fixed vertex pair be made long while keeping cube combinatorics, i.e. only $2n$ facets), the fixed-vertex-shadow question (shadows through a fixed vertex, equivalently every coherent monotone path from the $c$-minimum to the $c$-maximum), the every-shadow question (every two-dimensional projection at once), and the every-norm question (steepest edge exponential simultaneously for all norms). The fixed-vertex-shadow question was resolved affirmatively in July 2026 by Black and Xue, who constructed for each $d\ge 3$ a $(d+1)$-dimensional polytope with $(2d+1)(d+1)+1$ facets and an objective for which every coherent monotone path has length at least $2^{d-1}-1$ - the first lower bounds of this kind, obtained by gluing rotated copies of a polytope with a large shadow so that the relevant cones cover all directions.

Problem Statement

Determine, for each of the following three existence questions left open by Black (2026), whether the answer is yes (exhibit the family) or no (prove a universal polynomial guarantee). The common objective is to complete the robustness program for shadow-vertex and steepest-edge lower bounds: a worst-case family must defeat an entire parameterized family of pivot choices at once - every admissible projection, or every norm - rather than a single choice as in the classical constructions.

Q1 (cubes; journal Open Problem 11). For each $n\in\mathbb{N}$, does there exist an $n$-dimensional combinatorial cube $C_n$ for which every shadow path between a fixed pair of vertices of $C_n$ has superpolynomial length in $n$? (The author's arXiv formulation of the same question asks for length exponential in $n$; an exponential family answers both.)

Q2 (every shadow; journal Open Problem 13). Does there exist a family of polytopes for which every shadow - for every choice of two-dimensional projection - has exponentially many vertices? As noted in the source, this is equivalent to asking for a family of polytopes, closed under invertible linear transformations, for which the expected size of a random shadow is always exponential.

Q3 (all norms; journal Open Problem 14). Does there exist a family of linear programs for which the steepest-edge path is of exponential length for every norm simultaneously? A special case highlighted in the source as particularly interesting is the family of all norms of the form $\eta(x)=\|Ax\|_2$ with $A$ invertible. (The strictly broader variant for all continuous positively homogeneous normalizations simultaneously is stated in the source to be equivalent to the monotone variant of the polynomial Hirsch conjecture and is not required here.)

Q1, Q2, and Q3 are three independent open problems posed separately in the source (journal Open Problems 11, 13, and 14), with no stated interdependence. Each is a yes/no existence question: a positive answer is an explicit worst-case family, with a universality proof that it defeats the entire parameterized family of pivot choices at once, and a negative answer is an impossibility theorem establishing the corresponding universal polynomial guarantee - for Q1, that every combinatorial cube admits, for every fixed vertex pair, some polynomial-length shadow path between that pair; for Q2, that every polytope admits a two-dimensional projection whose shadow has polynomially many vertices; for Q3, that every linear program admits a norm for which the steepest-edge path has polynomial length.

References

1. Alexander E. Black. Exponential Lower Bounds for Many Pivot Rules for the Simplex Method. Mathematical Programming (online 28 January 2026). DOI 10.1007/s10107-026-02325-5; arXiv:2403.04886; preliminary version in IPCO 2025, DOI 10.1007/978-3-031-93112-3_7. https://arxiv.org/abs/2403.04886
2. Alexander E. Black and Lei Xue. Any Proof of Polynomial Hirsch Must be Completely Incoherent. arXiv:2607.11628 (2026). https://arxiv.org/abs/2607.11628
3. Alexander E. Black and Francisco Criado. Random Shadows of Fixed Polytopes. arXiv:2406.06936 (2024). https://arxiv.org/abs/2406.06936
4. Alexander E. Black and Raphael Steiner. Finding Short Paths on Simple Polytopes. arXiv:2603.05482 (2026). https://arxiv.org/abs/2603.05482
5. Yann Disser, Georg Loho, Matthew Maat and Nils Mosis. Lower bounds for ranking-based pivot rules. arXiv:2512.16684 (2025). https://arxiv.org/abs/2512.16684
6. Eleon Bach and Sophie Huiberts. Optimal Smoothed Analysis of the Simplex Method. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS 2025), pages 1829-1856. DOI 10.1109/FOCS63196.2025.00096; arXiv:2504.04197 (2025). https://arxiv.org/abs/2504.04197
7. Eleon Bach, Alexander E. Black, Sophie Huiberts and Sean Kafer. Beyond Smoothed Analysis: Analyzing the Simplex Method By-the-Book. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026), DOI 10.1145/3798129.3800742; arXiv:2510.21613 (2025). https://arxiv.org/abs/2510.21613
8. Louis J. Billera and Bernd Sturmfels. Fiber Polytopes. Annals of Mathematics 135, 527-549 (1992). DOI 10.2307/2946575. https://doi.org/10.2307/2946575
9. Katta G. Murty. Computational complexity of parametric linear programming. Mathematical Programming 19, 213-219 (1980). DOI 10.1007/BF01581642. https://doi.org/10.1007/BF01581642
10. Donald Goldfarb and William Y. Sit. Worst case behavior of the steepest edge simplex method. Discrete Applied Mathematics 1, 277-285 (1979). DOI 10.1016/0166-218X(79)90004-0. https://doi.org/10.1016/0166-218X(79)90004-0
11. Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. Journal of the ACM 51 (2004). DOI 10.1145/990308.990310. https://doi.org/10.1145/990308.990310