<p><a href="https://books.google.com.sa/books?id=RjB40FbSDo4C&amp;pg=PA83&amp;lpg=PA83&amp;dq=isomorphism+planes+designs+babai&amp;source=bl&amp;ots=h_4kwQ6zXo&amp;sig=mu4bhEvIBMiTRgQDvoksG1qmxbY&amp;hl=en&amp;sa=X&amp;redir_esc=y#v=onepage&amp;q=isomorphism%20planes%20designs%20babai&amp;f=false" rel="nofollow">Miller showed</a> 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.</p>

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

<p>Here, <em>hard</em> means the problem has no known polynomial-time algorithm.</p>

CC BY-SA 3.0
2016-05-20T16:48:04.440Z
Cross-posted to http://mathoverflow.net/questions/239382
Emil Jeřábek
CC BY-SA 3.0
2016-05-22T13:22:20.573Z
Babai and Luks extended Miller's result to show that isomorphism testing for symmetric designs can be done in $n^{O(\log \log n)}$. (Theorem 3.3) 
http://www.sciencedirect.com/science/article/pii/S0304020808729761
Mohammad Al-Turkistany
CC BY-SA 3.0
2016-05-28T17:43:27.990Z
Relatively recent paper by Huber suggests that Miller's algorithm is the best known algorithm (until 2010): http://www.sciencedirect.com/science/article/pii/S0097316510001044
Mohammad Al-Turkistany
<cc.complexity-theory><graph-isomorphism>
Testing Isomorphism of projective planes
Mohammad Al-Turkistany
# Testing Isomorphism of projective planes

(Asked by: username_0 on 2016-05-16)

[Miller showed](https://books.google.com.sa/books?id=RjB40FbSDo4C&pg=PA83&lpg=PA83&dq=isomorphism+planes+designs+babai&source=bl&ots=h_4kwQ6zXo&sig=mu4bhEvIBMiTRgQDvoksG1qmxbY&hl=en&sa=X&redir_esc=y#v=onepage&q=isomorphism%20planes%20designs%20babai&f=false) 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.

**Tags:** cc.complexity-theory, graph-isomorphism
> **Comments:**
> **username_1**: Cross-posted to http://mathoverflow.net/questions/239382  
> **username_0**: Babai and Luks extended Miller's result to show that isomorphism testing for symmetric designs can be done in $n^{O(\log \log n)}$. (Theorem 3.3)  http://www.sciencedirect.com/science/article/pii/S0304020808729761  
> **username_0**: Relatively recent paper by Huber suggests that Miller's algorithm is the best known algorithm (until 2010): http://www.sciencedirect.com/science/article/pii/S0097316510001044  

---

## 0 answers

