Spielman and Teng (JACM ?04), proved that the smoothed complexity of a two-phase shadow-vertex method for linear programming is polynomial in the number of constraints n, the number of variables d, and the parameter of perturbation 1/\sigma. The key geometric result in their proof was an upper bound of o(nd^3 /\min (\sigma ,(9d\ln n)^{ - 1/2} )^6 ) on the expected size of the shadow of the polytope de?ned by the perturbed linear program. In this paper, we give a much simpler proof of a better bound: o(n^3 d\ln n/\min (\sigma ,(4d\ln n)^{ - 1/2} )^2 )
When evaluated at \sigma = (9d\ln n)^{ - 1/2}, this improves the size estimate from O(nd^6 \ln ^3 n) to o(n^2 d^2 \ln n). The improvement only becomes better as s decreases.