# Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Nov 2022.

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

- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [Exact objectives of random linear programs and mean widths of random polyhedrons](https://mlsanity.com/paper/2403.03637/) (2024)

## Abstract (arXiv)

The simplex method for linear programming is known to be highly efficient in practice, and understanding its performance from a theoretical perspective is an active research topic. The framework of smoothed analysis, first introduced by Spielman and Teng (JACM '04) for this purpose, defines the smoothed complexity of solving a linear program with d variables and n constraints as the expected running time when Gaussian noise of variance σ2 is added to the LP data. We prove that the smoothed complexity of the simplex method is O(σ-3/2 d13/4log7/4 n), improving the dependence on 1/σ compared to the previous bound of O(σ-2 d2√log n). We accomplish this through a new analysis of the shadow bound, key to earlier analyses as well. Illustrating the power of our new method, we use our method to prove a nearly tight upper bound on the smoothed complexity of two-dimensional polygons. We also establish the first non-trivial lower bound on the smoothed complexity of the simplex method, proving that the shadow vertex simplex method requires at least Omega Big(min big(σ-1/2 d-1/2log-1/4 d,2d big) Big) pivot steps with high probability. A key part of our analysis is a new variation on the extended formulation for the regular 2k-gon. We end with a numerical experiment that suggests this analysis could be further improved.