The smoothed analysis of algorithms is concerned with the expected running time of
an algorithm under slight random perturbations of arbitrary inputs. Spielman and Teng
proved that the shadow-vertex simplex method has polynomial smoothed complexity. On a
slight random perturbation of an arbitrary linear program, the simplex method finds the
solution after a walk on polytope(s) with expected length polynomial in the number of
constraints n, the number of variables d and the inverse standard deviation of the
perturbation 1/sigma. We show that the length of walk in the simplex method is actually
polylogarithmic in the number of constraints n. Spielman-Teng's bound on the walk was
O(n^{86} d^{55} sigma^{-30}), up to logarithmic factors. We improve this to O(log^7 n (d^9
+ d^3 \s^{-4})). This shows that the tight Hirsch conjecture n-d on the length of walk on
polytopes is not a limitation for the smoothed Linear Programming. Random perturbations
create short paths between vertices. We propose a randomized phase-I for solving arbitrary
linear programs, which is of independent interest. Instead of finding a vertex of a
feasible set, we add a vertex at random to the feasible set. This does not affect the
solution of the linear program with constant probability. This overcomes one of the major
difficulties of smoothed analysis of the simplex method -- one can now statistically
decouple the walk from the smoothed linear program. This yields a much better reduction of
the smoothed complexity to a geometric quantity -- the size of planar sections of random
polytopes. We also improve upon the known estimates for that size, showing that it is
polylogarithmic in the number of vertices.