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 StepsIs Bounded between Two Quadratic Functionsof 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 Average-case Complexity of Simplex Algorithm
cc.complexity theory;linear programming;convex optimization;average case complexity;simplex