Miller showed that isomorphism testing of projective planes can be done in $v^{O(\log \log v)}$. I would like to know whether Babai's techniques that led to the quasipolynomial time algorithm for GI would colapse isomorphism testing for projective planes to polynomial time.

Is Miller's algorithm still the best known upper-bound? What other natural hard problems can be solved in $n^{O(\log \log n)}$ time?

Here, hard means the problem has no known polynomial-time algorithm.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.