# Short-step Methods Are Not Strongly Polynomial-Time

arXiv: https://arxiv.org/abs/2201.02768 · HTML: https://mlsanity.com/paper/2201.02768/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jan 2022.

## Built on by (most cited first, 3 of 3)

- [On the Sample Complexity of Imitation Learning for Smoothed Model Predictive Control](https://mlsanity.com/paper/2306.01914/) (2023)
- [Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity](https://mlsanity.com/paper/2208.03811/) (2022)
- [Improved Sample Complexity of Imitation Learning for Barrier Model Predictive Control](https://mlsanity.com/paper/2410.00859/) (2024)

## Abstract (arXiv)

Short-step methods are an important class of algorithms for solving convex constrained optimization problems. In this short paper, we show that under very mild assumptions on the self-concordant barrier and the width of the ℓ2-neighbourhood, any short-step interior-point method is not strongly polynomial-time.