Bento Natura

We prove a strongly polynomial bound on the circuit diameter of polyhedra, resolving the circuit analogue of the polynomial Hirsch conjecture. Specifically, we show that the circuit diameter of a polyhedron $P = \{x \in \mathbb{R}^n : Ax = b, x \geq 0\}$ with $A \in \mathbb{R}^{m \times n}$ is $O(m^2 \log m)$. Our construction yields monotone circuit walks, giving the same bound for the monotone circuit diameter.
The circuit diameter, introduced by Borgwardt, Finhold, and Hemmecke (SIDMA 2015), is a natural relaxation of the combinatorial diameter that allows steps along circuit directions rather than only along edges. All prior upper bounds on the circuit diameter were only weakly polynomial. Finding a circuit augmentation algorithm that matches this bound would yield a strongly polynomial time algorithm for linear programming, resolving Smale's 9th problem.

We present improved running time and iteration complexities of interior point methods for linear programs parametrized by the straight line complexity, i.e., the minimum number of segments of any piecewise linear curve traversing a particular neighborhood of the central path. While the standard measure of progress is the reduction in duality gap, the straight line complexity provides a stronger instance-wise bound, reflecting the combinatorial structure of the problem.
Our first main result is a wide neighborhood interior point method whose running time is the wide-neighborhood straight line complexity times current matrix multiplication time, improving in essence a factor $n$ over the algorithm by Allamigeon, Dadush, Loho, Natura, and Végh (SIAM J. Comput. 2025). The algorithm can be seen as a boosted version of the robust interior point methods of Cohen, Lee and Song (JACM 2021) and van den Brand (SODA 2020) that can reduce the gap by a polynomial factor in current matrix multiplication time. Our algorithm is also able to traverse any near-linear segments of the central path in current matrix multiplication time, independently of the length of the segment.
Our second main result focuses on interior point methods that stay in the narrow $\ell_2$-neighborhood. We give a much stronger analysis of the $\ell_2$-trust region interior point method introduced by Lan, Monteiro and Tsuchiya (SIAM J. Optim. 2009), showing that it is approximately instance optimal in this neighborhood: the number of iterations is within a constant factor of the lower bound.
A main ingredient in both methods are trust region subroutines with $\ell_\infty$ and $\ell_2$-constraints, respectively. We develop fast and strongly polynomial algorithms for solving both these problems to high accuracy. In the $\ell_2$-setting, this answers an open question by Lan, Monteiro and Tsuchiya.

We develop a new interior point method for solving linear programs. Our algorithm is universal in the sense that it matches the number of iterations of any interior point method that uses a self-concordant barrier function up to a factor $O(n^{1.5}\log n)$ for an $n$-variable linear program in standard form.
The running time bounds of interior point methods depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound. Our algorithm also admits a combinatorial upper bound, terminating with an exact solution in $O(2^{n} n^{1.5}\log(n))$ iterations. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations.

We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two non-zero entries per row, or at most two non-zero entries per column. Primal and dual feasibility were shown by Megiddo (SICOMP '83) and Végh (MOR '17) respectively. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale's 9th problem. Our approach is based on the recent primal-dual interior point method (IPM) due to Allamigeon, Dadush, Loho, Natura and Végh (FOCS '22). The number of iterations needed by the IPM is bounded, up to a polynomial factor in the number of inequalities, by the straight line complexity of the central path. Roughly speaking, this is the minimum number of pieces of any piecewise linear curve that multiplicatively approximates the central path. As our main contribution, we show that the straight line complexity of any minimum cost generalized flow instance is polynomial in the number of arcs and vertices. By applying a reduction of Hochbaum (ORL '04), the same bound applies to any linear program with at most two non-zeros per column or per row. To be able to run the IPM, one requires a suitable initial point. For this purpose, we develop a novel multistage approach, where each stage can be solved in strongly polynomial time given the result of the previous stage. Beyond this, substantial work is needed to ensure that the bit complexity of each iterate remains bounded during the execution of the algorithm. For this purpose, we show that one can maintain a representation of the iterates as a low complexity convex combination of vertices. Our approach is black-box and can be applied to any log-barrier path following method.