Preprints

2026

1. Circuit Diameter of Polyhedra is Strongly Polynomial

   Bento Natura

   Preprint

   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.

   @misc{natura2026circuitdiameterpolyhedrastrongly,
     author = {Natura, Bento},
     title = {Circuit Diameter of Polyhedra is Strongly Polynomial},
     year = {2026},
     eprint = {2602.06958},
     archiveprefix = {arXiv},
     primaryclass = {math.OC},
   }