Skip to main content
update on quasipolynomial time analysis
Source Link

An update from Babai:

http://people.cs.uchicago.edu/~laci/update.html

The main result, which appears to have been vetted at this point with extreme care, has weakened somewhat. His bound is now $\exp(n^{o(1)})$, a big improvement over the previous $\exp(n^{1/2 + o(1)})$, but no longer quasi-polynomial.

UPDATE: Babai is now claiming a new Split-or-Johnson subroutine restores the quasipolynomial claim! http://people.cs.uchicago.edu/~laci/update.html

An update from Babai:

http://people.cs.uchicago.edu/~laci/update.html

The main result, which appears to have been vetted at this point with extreme care, has weakened somewhat. His bound is now $\exp(n^{o(1)})$, a big improvement over the previous $\exp(n^{1/2 + o(1)})$, but no longer quasi-polynomial.

An update from Babai:

http://people.cs.uchicago.edu/~laci/update.html

The main result, which appears to have been vetted at this point with extreme care, has weakened somewhat. His bound is now $\exp(n^{o(1)})$, a big improvement over the previous $\exp(n^{1/2 + o(1)})$, but no longer quasi-polynomial.

UPDATE: Babai is now claiming a new Split-or-Johnson subroutine restores the quasipolynomial claim! http://people.cs.uchicago.edu/~laci/update.html

Source Link

An update from Babai:

http://people.cs.uchicago.edu/~laci/update.html

The main result, which appears to have been vetted at this point with extreme care, has weakened somewhat. His bound is now $\exp(n^{o(1)})$, a big improvement over the previous $\exp(n^{1/2 + o(1)})$, but no longer quasi-polynomial.

Post Made Community Wiki by anonymous_coward