{"id":"arxiv/2602.06958","url":"https://arxiv.org/abs/2602.06958","tags":["math.OC","cs.DS"],"score":0,"title":"Circuit Diameter of Polyhedra is Strongly Polynomial","domain":"math.OC","source":"arxiv","authors":["Bento Natura"],"reviews":0,"subject":"math.OC","summary":"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:\\, A x = b, \\, x \\ge 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-06","reactions":{}}