The Average-case Complexity of Simplex Algorithm I was wondering if there are any results on the average case complexity of the simplex algorithm. Let $A \in \mathbb{R}^{m \times n}$ be the matrix in the linear constraint.  I know that Smale did some work in the 80's that says that if we fix $m$, then the average complexity is linear in $n$ when $n$ goes to infinity.

However, by duality theory, $m$ and $n$ are symmetric in LP. Also in the 80's, Adler et al. showed that the expected number of pivots is quadratic in $\min \{ m, n\}$. (See ``A Simplex Algorithm Whose Average Number of Steps
Is Bounded between Two Quadratic Functions
of the Smaller Dimension '') And they even showed a quadratic lower bound.

I was wondering if there are any recent development on such average-case analysis.
The first thing that comes to mind is "Smoothed Analysis" of Spielman and Teng: arxiv.org/pdf/cs/0111050.pdf. Their main result is Theorem 5.0.1, which bounds the expected (over "typical instances") runtime of a version of the Simplex algorithm by a polynomial, though the degree of the polynomial is not stated there.