Smoothed Complexity of the Simplex Method

§ Problem Statement

Setup

Fix integers $n \ge 1$ (variables) and $m \ge n$ (constraints). Consider linear programs

\max_{x \in \mathbb R^n} c^\top x \quad \text{subject to} \quad Ax \le b,

with $A \in \mathbb R^{m \times n}$ , $b \in \mathbb R^m$ , $c \in \mathbb R^n$ . A simplex pivot rule $R$ means a complete deterministic specification of entering/leaving choices (including tie-breaking and initialization details), so the pivot count is well defined on nondegenerate instances.

Convention for this problem: in the Gaussian smoothed model, an adversary chooses $(\bar A,\bar b,\bar c)$ with $\|(\bar A,\bar b,\bar c)\|\le 1$ , then independent Gaussian noise is added to every scalar coefficient of $A,b,c$ :

A=\bar A+G,\qquad b=\bar b+h,\qquad c=\bar c+g,

where entries of $G,h,g$ are i.i.d. $N(0,\sigma^2)$ with $\sigma\in(0,1]$ . Let $T_R(A,b,c)$ be the total number of pivots performed by the full simplex algorithm using rule $R$ . Define

\mathrm{Sm}_R(m,n,\sigma):=\sup_{\|(\bar A,\bar b,\bar c)\|\le 1}\ \mathbb E\!\left[T_R(\bar A+G,\bar b+h,\bar c+g)\right].

Unsolved Problem

Does there exist a pivot rule $R$ with near-linear smoothed complexity (up to polylogarithmic factors), uniformly for all $m\ge n$ and $\sigma\in(0,1]$ ; for example

\mathrm{Sm}_R(m,n,\sigma)\le O\!\left(n\cdot \mathrm{polylog}(m,n,1/\sigma)\right)?

More generally, what is the correct asymptotic order of

\inf_R \mathrm{Sm}_R(m,n,\sigma)

as a function of $m,n,\sigma$ under this perturbation model?

§ Discussion

Loading discussion…

§ Significance & Implications

The simplex method is the most widely used algorithm for linear programming, and its strong practical performance has motivated decades of theory. Spielman & Teng (2004) established polynomial smoothed complexity for shadow vertex, and later work substantially improved parameter dependence. However, current upper and lower bounds are still separated, and a tight characterization of optimal smoothed complexity across pivot rules remains open.

§ Known Partial Results

Spielman & Teng (2004): first polynomial smoothed bound for a shadow-vertex simplex algorithm (with very large exponents).
Dadush & Huiberts (2018): major simplification and improvement; STOC-version bound includes a $d^5$ term (often cited as roughly $O(d^2\sqrt{\log n}\,\sigma^{-2}+d^5\log^{3/2}n)$ ).
Huiberts et al. (2023): improved upper bound to $O(\sigma^{-3/2} d^{13/4}\log^{7/4} n)$ and proved a first non-trivial lower bound for shadow-vertex simplex in the smoothed setting.
Huiberts et al. (2025): journal version consolidating and extending the STOC 2023 analysis.
Spielman et al. (2004): Despite this progress, the optimal dependence on $(m,n,\sigma)$ for the best pivot rule is still not tightly characterized.