Random walks on polytopes and an affine interior point method for linear programming.

Ravi Kannan, Hariharan Narayanan

Browse the full STOC paper archive.