The simplex algorithm is one of the most widely used algorithms for solving linear programs in practice. It's worst case complexity, however, with essentially all known deterministic pivoting rules is exponential. There is, however, a randomized pivoting rule, called Random-Facet, discovered independently by Kalai and by Matousek, Sharir and Welzl, under which the expected running time of the simplex algorithm is subexponential. We obtain subexponential lower bounds for Random-Facet and two other randomized pivoting rules.

Joint work with Thomas Dueholm Hansen and Oliver Friedmann