yes, Dan has a randomized simplex with polynomial time. I don't remember the details, but the paper (not paywalled) can be found here http://www.cs.yale.edu/hom

yes, Dan has a randomized simplex with polynomial time. I don't remember the details, but the paper (not paywalled) can be found here http://www.cs.yale.edu/homes/spielman/Research/SimplexStoc.pdf http://www.cs.yale.edu/homes/spielman/Research/SimplexStoc.p... It was published around 2009 or so, iirc.