Combinatorics of the interior-point counterexample polytope $\mathrm{CEX}_n(t)$: the $n$-cube conjecture and the vertex–tropical-segment correspondence

The STOC 2022 paper of Allamigeon, Gaubert and Vandame proved that no interior point method (IPM) based on a self-concordant barrier can be strongly polynomial for linear programming: on an explicit family $\mathrm{CEX}_n(t)$ of linear programs in dimension $n$ with exactly $2n$ constraints, the log-limit (tropicalization) of the central path, which is independent of the barrier, degenerates to a piecewise-linear curve consisting of $2^n-1$ tropical segments, forcing at least $2^n-1$ iterations. The paper leaves the combinatorics of the counterexample polytope itself open: it conjectures, based on face-lattice computations for $n\le 5$ and on lemmas showing that its inequalities are paired like opposite cube facets, that the feasible set of $\mathrm{CEX}_n(t)$ is combinatorially equivalent to the $n$-cube for $t$ sufficiently large, and it asks for a full study of the correspondence between the polytope's $2^n$ vertices and the $2^n$ extremities of the tropical segments of the tropical central path. This record poses that two-part combinatorial question: prove or refute (i) the combinatorial equivalence of the feasible polytope of $\mathrm{CEX}_n(t)$ with the $n$-cube for all sufficiently large $t$, and (ii) the bijection between its $2^n$ vertices and the $2^n$ tropical-segment extremities, each extremity arising as the tropicalization (exponent vector) of a distinct vertex. The source's companion algorithmic direction, finding a trajectory to the optimum that does not degenerate to the tropical boundary, lacks a sharp completion boundary.

Background

Linear programming (LP) is solvable in polynomial time by interior point methods (IPMs), but standard IPM complexity bounds depend on the bit size $L$ of the input numbers. An LP algorithm is called strongly polynomial if its number of arithmetic operations is bounded by a polynomial in the number of numerical inputs only, independent of $L$; whether LP admits a strongly polynomial algorithm is Smale's ninth problem for the twenty-first century and one of the major open problems of computational optimization. For the simplex method, worst-case behavior is classical: on the Klee–Minty cube, a deformed $n$-dimensional cube on which a natural pivot rule visits all $2^n$ vertices, the method takes exponentially many steps.

IPMs approach the optimum through the interior of the feasible set $K$. They trace (an approximation of) the central path: the curve of minimizers of the penalized objectives $\eta\langle c,x\rangle+f(x)$ for $\eta>0$, where $f$ is a barrier, i.e., a smooth strictly convex function on the interior of $K$ that tends to $+\infty$ at the boundary. The classical theory of Nesterov and Nemirovskii rests on self-concordant barriers, meaning barriers whose third derivative is controlled by the Hessian in a specific way that makes damped Newton steps provably convergent; every convex body admits one, and path-following IPMs built on them run in time polynomial in the square root of the barrier's complexity parameter and in $\log(1/\varepsilon)$, where $\varepsilon$ is the target accuracy.

Allamigeon, Benchimol, Gaubert and Joswig (2018) proved that the logarithmic barrier ($-\sum_i\log x_i$ on the positive orthant) cannot yield a strongly polynomial IPM, by tropical geometry. Tropicalization means applying the map $x\mapsto\log_t x$ coordinatewise, with base $t$ tending to infinity: a polytope whose vertex coordinates are rational functions of $t$ then converges, after this rescaling, to a tropical polyhedron, a set defined by linear inequalities over the tropical (max-plus) semiring $\mathbb{R}\cup\{-\infty\}$, where addition is the maximum and multiplication is the ordinary sum. The central path degenerates in this limit to a piecewise-linear curve, the tropical central path. A tropical segment is the tropical convex hull of two points (itself a piecewise-linear curve), and its two endpoints are called its extremities; the number of tropical segments needed to describe the tropical central path lower-bounds the iterations of any method whose trajectory stays in a suitable multiplicative neighborhood of the central path, i.e., a set of points whose coordinates are within fixed multiplicative factors of those of a central path point. The obstruction is that the tropical central path can lie on the boundary of the tropicalized feasible set, forcing it to bend exponentially often.

Allamigeon, Gaubert and Vandame (STOC 2022) extended this impossibility from the logarithmic barrier to every self-concordant barrier. They construct a parametric family of LPs, written $\mathrm{CEX}_n(t)$ ('cex' for counterexample), in dimension $n$ with exactly $2n$ constraints, the same shape as the Klee–Minty cube. It is the problem of minimizing $x_n$ subject to

$t^{-u_i}\sum_{j=1}^{i-1}x_j+t^{-u_{i+1}+1}x_i\;\le\;\sum_{j=i+1}^{n-1}t^{-u_j}x_j+x_n+t^{-u_n},\qquad i=1,\dots,n-1$

$\sum_{j=1}^{n}x_j\le 1,\qquad 0\le x_1\le x_2\le\dots\le x_{n-1}\le t^{u_n}x_n$

where $u_k:=3\cdot 2^{k-2}-1$ for all $k\ge 1$ (the value $u_1$ never enters nontrivially, as it multiplies an empty sum) and $t>1$. The input bit size is $L=\Omega(u_n\log_2 t)$. Their Theorem 1 states that for $t$ sufficiently large, every interior point method based on any self-concordant barrier requires at least $2^n-1$ iterations on $\mathrm{CEX}_n(t)$ to reduce the objective from $\Omega(1)$ to $1/2^{2L}$. The mechanism is that the tropical central path of $\mathrm{CEX}_n(t)$, which is independent of the barrier, is the concatenation of exactly $2^n-1$ tropical segments (Theorem 24 of the paper): it is built recursively from two copies of the $(n-1)$-dimensional tropical central path located near two disjoint facets, plus one extra tropical segment, in deliberate analogy with the simplex path on the Klee–Minty cube.

The paper leaves the combinatorial structure of the counterexample itself open. The authors prove that the two special facets $\sum_j x_j=1$ and $x_{n-1}=t^{u_n}x_n$ are disjoint for $t$ large, and that the inequalities of $\mathrm{CEX}_n(t)$ are 'paired, like in a cube' (Lemma 34 of the paper: each of the $n-1$ constraint pairs defines two disjoint facets). They computed the face lattice of the feasible polytope for $n\le 5$ and found the combinatorial type of the $n$-cube each time. On this evidence they conjecture that the feasible set of $\mathrm{CEX}_n(t)$ is combinatorially equivalent to the $n$-cube (i.e., has the same face lattice as the cube $\{0,1\}^n$, hence $2^n$ vertices and $2n$ facets) for $t$ sufficiently large, write that the proof of this is 'left for a further work', and state in their conclusion that the combinatorics of the feasible set 'is yet to be fully studied, in particular, the correspondence between the vertices and the $2^n$ extremities of the tropical segments in the tropical central path'. Since the tropical central path has $2^n-1$ tropical segments, it has $2^n$ extremities; and each vertex of the polytope, its coordinates being rational functions of $t$ with coordinatewise asymptotics $\Theta(t^{\alpha})$, has a well-defined tropicalization (its exponent vector). The conjectured correspondence is thus a putative bijection between $2^n$ classical vertices and $2^n$ tropical endpoints. Establishing it would give the vertex-level, Klee–Minty-style explanation of why the tropical central path bends exponentially often, which is the engine of the paper's lower bound.

Problem Statement

Determine the combinatorics of the feasible set of the counterexample family $\mathrm{CEX}_n(t)$ of Allamigeon, Gaubert and Vandame, as explicitly left open in their paper. Two linked claims must be proved or refuted.

(1) The $n$-cube conjecture. For every $n\ge 2$ (the constraint family is degenerate for $n=1$), is the feasible polytope of $\mathrm{CEX}_n(t)$, i.e., the set of $(x_1,\dots,x_n)$ satisfying

$t^{-u_i}\sum_{j=1}^{i-1}x_j+t^{-u_{i+1}+1}x_i\;\le\;\sum_{j=i+1}^{n-1}t^{-u_j}x_j+x_n+t^{-u_n},\qquad i=1,\dots,n-1$

$\sum_{j=1}^{n}x_j\le 1,\qquad 0\le x_1\le x_2\le\dots\le x_{n-1}\le t^{u_n}x_n$

with $u_k=3\cdot 2^{k-2}-1$ for all $k\ge 1$ and $t>1$, combinatorially equivalent to the $n$-dimensional cube for all sufficiently large $t$? Equivalently: does its face lattice coincide with that of $\{0,1\}^n$, so that it has exactly $2^n$ vertices and $2n$ facets? The source conjectures yes, with the face lattice verified computationally for $n\le 5$ and with the paired-facet disjointness lemmas as partial evidence; the proof is explicitly left open.

(2) The vertex–extremity correspondence. In the tropical limit $t\to\infty$, the tropical central path of $\mathrm{CEX}_n(t)$ is the concatenation of exactly $2^n-1$ tropical segments and therefore has $2^n$ extremities. Do these $2^n$ extremities stand in bijection with the $2^n$ vertices of the feasible polytope, in the sense that each extremity is the coordinatewise $\log_t$-limit, i.e., the exponent vector of the $\Theta(t^{\alpha})$ asymptotics, of a distinct vertex, and every vertex arises this way? Establish this correspondence rigorously, or refute it for some dimension.

Scope note: the same paper also proposes the broader algorithmic direction of identifying a trajectory to the optimal solution that cannot degenerate to the boundary of the tropical feasible set ('that remains central in the tropical sense'). That direction is a research program without a sharp completion boundary; it is deliberately not part of the completion boundary of the problem posed here.

References

1. Xavier Allamigeon, Stéphane Gaubert, Nicolas Vandame. No self-concordant barrier interior point method is strongly polynomial. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), ACM, pp. 515–528, 2022. DOI: 10.1145/3519935.3519997, https://doi.org/10.1145/3519935.3519997
2. Xavier Allamigeon, Stéphane Gaubert, Nicolas Vandame. No self-concordant barrier interior point method is strongly polynomial. arXiv:2201.02186, 2022 (full version with appendices; v1 of 6 January 2022 is the only version). https://arxiv.org/abs/2201.02186
3. Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig. Log-barrier interior point methods are not strongly polynomial. SIAM Journal on Applied Algebra and Geometry 2(1):140–178, 2018. DOI: 10.1137/17m1142132, https://doi.org/10.1137/17m1142132
4. Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig. What tropical geometry tells us about the complexity of linear programming. SIAM Review 63(1):123–164, 2021. DOI: 10.1137/20M1380211, https://doi.org/10.1137/20M1380211
5. Xavier Allamigeon, Daniel Dadush, Georg Loho, Bento Natura, László A. Végh. Interior point methods are not worse than Simplex. SIAM Journal on Computing 54(5), 2025 (published online 3 March 2025). DOI: 10.1137/23M1554588, https://doi.org/10.1137/23M1554588 (arXiv:2206.08810, https://arxiv.org/abs/2206.08810)
6. Manru Zong, Yin Tat Lee, Man-Chung Yue. Short-step methods are not strongly polynomial-time. Mathematical Programming 207(1–2):733–746, 2024. DOI: 10.1007/s10107-023-02002-x, https://doi.org/10.1007/s10107-023-02002-x (arXiv:2201.02768, 2022, https://arxiv.org/abs/2201.02768)
7. Antoine Deza, Eissa Nematollahi, Tamás Terlaky. How good are interior point methods? Klee–Minty cubes tighten iteration-complexity bounds. Mathematical Programming 113(1):1–14, 2008 (published online 21 October 2006). DOI: 10.1007/s10107-006-0044-x, https://doi.org/10.1007/s10107-006-0044-x
8. Yurii Nesterov, Arkadii Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programming. SIAM, 1994. DOI: 10.1137/1.9781611970791, https://doi.org/10.1137/1.9781611970791
9. Adrian Vladu. Breaking the barrier of self-concordant barriers: faster interior point methods for M-matrices. Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), ACM, pp. 2213–2224, 2025. DOI: 10.1145/3717823.3718255, https://doi.org/10.1145/3717823.3718255 (arXiv:2504.20619, https://arxiv.org/abs/2504.20619)
10. Daniel Dadush, Haoyuan Ma, Bento Natura, László A. Végh. Trust region interior point methods: optimal ℓ₂- and faster wide-neighborhood path following. Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026), ACM, pp. 755–766, 2026. DOI: 10.1145/3798129.3800790, https://doi.org/10.1145/3798129.3800790
11. Daniel Dadush, Stefan Kober, Zhuan Khye Koh. On circuit diameter and straight line complexity. arXiv:2602.05699, 2026. https://arxiv.org/abs/2602.05699
12. Steve Smale. Mathematical problems for the next century. The Mathematical Intelligencer 20(2):7–15, 1998. DOI: 10.1007/BF03025291, https://doi.org/10.1007/BF03025291
13. Victor Klee, George J. Minty. How good is the simplex algorithm? In: Inequalities III (Proc. Third Symposium on Inequalities, Los Angeles, 1969), Academic Press, pp. 159–175, 1972. zbMATH: 3466805, https://zbmath.org/?q=an%3A3466805