Smoothed simplex complexity: optimal dimension dependence (now O(σ^(−1/2) d^(11/4) log^(7/4) n))
The first 25 years of progress reduced exponents dramatically and the noise dependence is now proved optimal; what remains is the dimension exponent and extension to real pivot rules, which are technical but seem attackable, so difficulty is in the hard-but-visible band. Application value is moderate, as an explanation of solver behaviour. Leverage is limited to LP theory.
The problem
Why does simplex almost always run fast? Pin down how its typical cost grows with the number of variables.
- 1Simplex hops corner to corner
- 2Worst cases are astronomically slow
- 3Add small noise: worst cases vanish
- 4Noise dependence now shown optimal
- 5Open: tight dependence on dimension
Setting. Consider the linear program subject to , with ( constraints, variables). Perturb each row by independent Gaussian noise of standard deviation . The of a simplex variant is the maximum, over all inputs, of the number of pivots (hops) on the perturbed input. Smoothed analysis interpolates between worst case () and average case (large ).
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- Fast matrix multiplicationAlgorithm
- Step 4
- Linear programmingAlgorithm · host
- Then
- Smoothed simplex complexity: optimal dimension dependence (now O(σ^(−1/2) d^(11/4) log^(7/4) n))The problem
State of the art
Upper bounds. Spielman and Teng's original bound was ; Deshpande and Spielman (2005), Vershynin (2009), Dadush and Huiberts (2018, SIAM J. Comput. 2020), Huiberts, Lee and Zhang (STOC 2023, ) and Bach and Huiberts (arXiv:2504.04197, April 2025, ) improved it. Bach and Huiberts also proved a high-probability lower bound on the combinatorial diameter after smoothing, so is optimal among all simplex methods up to polylogarithmic factors, while the dimension exponent is open between and . A 2025 follow-up by Bach, Black, Huiberts and Kafer (arXiv:2510.21613) proposes an analysis framework "by the book" using properties of real LPs.
Realistic applications
A tight, rule-specific smoothed analysis would explain, with a theorem, why simplex runs in near-linear iterations in practice on real LPs, and would guide pivot-rule and pre-conditioning design in solvers (Gurobi, HiGHS, CPLEX). It would not give a strongly polynomial algorithm.
What counts as solved
A theorem giving matching upper and lower bounds on smoothed pivot count up to polylogarithmic factors in and for a shadow-vertex variant, or a smoothed polynomial bound for a pivot rule used in practice (Dantzig's rule or steepest edge).
How it gets verified
Expert reviewOnly expert review of the argument is possible today.
The target is matching upper and lower bounds (up to polylog factors) on smoothed pivot count for a shadow-vertex variant, or a smoothed polynomial bound for a pivot rule used in practice. This is a probabilistic geometry theorem outside Mathlib, so experts review it. Experiments on random perturbed LPs can illustrate scaling but do not prove it.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
Probabilistic geometry of random polytopes; numerical experiments on pivot counts test conjectured exponents.
Bottlenecks
ranked by votes- #1TheoryPractical pivot rules are not shadow-vertex
Dantzig and steepest-edge rules choose pivots locally, without the two-dimensional projection structure that powers all current analyses.
Community grades
Sign in to add your own grade.
Connected problems
No connections yet.
Progress
- Oct 24, 2025Analysis by the booksource
Bach, Black, Huiberts and Kafer introduced a framework beyond smoothed analysis.
- Apr 5, 2025Optimal noise dependencesource
Bach and Huiberts proved O(σ^(-1/2) d^(11/4) log^(7/4) n) with a matching lower bound in σ.
- Nov 14, 2017Friendly smoothed analysissource
Dadush and Huiberts simplified and improved the analysis (arXiv 2017; STOC 2018).
- Jul 6, 2001Smoothed analysis of simplexsource
Spielman and Teng proved polynomial smoothed complexity (STOC 2001; J. ACM 2004).