This is an announcement for the paper "Beyond Hirsch Conjecture: walks on random polytopes and smoothed complexity of the simplex method" by Roman Vershynin. Abstract: 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 had polynomial smoothed complexity. On a slight random perturbation of 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(min(d^5 log^2(n), d^9 log^4(d), d^3 sigma^{-4})). This shows that the tight Hirsch conjecture n-d on the 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. 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. So, in expectation it takes a constant number of independent trials until a correct solution is found. 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. Archive classification: Data Structures and Algorithms; Functional Analysis Remarks: 17 pages The source file(s), , is(are) stored in gzipped form as with size . The corresponding postcript file has gzipped size . Submitted from: vershynin@math.ucdavis.edu The paper may be downloaded from the archive by web browser from URL http://front.math.ucdavis.edu/cs.DS/0604055 or http://arXiv.org/abs/cs.DS/0604055 or by email in unzipped form by transmitting an empty message with subject line uget 04055 or in gzipped form by using subject line get 04055 to: math@arXiv.org.