A randomized polynomial time simplex algorithm for LP

http://theory.csail.mit.edu/~kelner/
http://theory.csail.mit.edu/~kelner/PDFs/KelnerSpielmanSimplex.pdf