3 ms·

thanks, it seems to be quite complex though, as far as I understand it's still "only" an expected polynomial algorithm given some assumptions about the input, a

thanks, it seems to be quite complex though, as far as I understand it's still "only" an expected polynomial algorithm given some assumptions about the input, and not a truly worst-case polynomial algorithm - as opposed to e.g. the ellipsoid method which is actually worst-case polynomial.

eru 6y ago
As far as I understand it's runs in expected polynomial time regardless of input. No assumptions on the input necessary. The expectation is over the choice of random bits created while running the algorithm.