# Are there any problems whose best known algorithms have running time $n^{\log \log n}$?

It’s well known that problems such as integer factorization have running times contained in $$e^{\text{Poly} \log }$$ which is the same $$n^{ \text{Poly} \log }$$ (actually the log term is itself in a cube root for integer factorization)

So this got me wondering about complexity classes that live between polynomial time and $$e^{\text{Poly} \log }$$ namely $$e^{\log \cdot \text{Poly} \log \log }$$ or $$n^{\text{Poly} \log \log}$$ as the title puts it.

Are there any problems whose best known algorithms live in this runtime complexity?

• Integer factorization is most certainly not known to have quasipolynomial-time ($n^{(\log n)^c}$) algorithms. This would break a lot of public key cryptography, for a start. The best known factoring algorithms are exponential-time ($2^{n^\epsilon}$, for $\epsilon\approx1/3$; some people falsely advertize this as “subexponential”). Jun 21 at 11:08
• My apologies I made the mistake of n in my polylog statement being the number and not the input size Jun 21 at 11:25
• See the notation here: en.m.wikipedia.org/wiki/… in section “current state of the art” Jun 21 at 11:27
• Yes, the wikipedia article misleadingly uses $n$ for the number itself rather than the length of the input. Jun 21 at 11:30
• What about how many primes numbers there up to n^(log(log(n))?
– Shaq
Jun 23 at 12:20

The best-known deterministic algorithm for testing polynomial identities given by depth-three diagonal circuits has running time $$n^{O(\log \log n)}$$ [1].
More explicitly, we are given an expression of the form $$f(x_1,\ldots,x_n) = \sum_{i=1}^s (a_{i,0} + a_{i,1} x_1 + \cdots + a_{i,n} x_n)^{d_i}$$ and we want to test if $$f(x_1,\ldots,x_n)$$ is the identically zero polynomial. Forbes, Shpilka, and Saptharishi gave a deterministic algorithm for this problem that runs in time $$\mathsf{poly}(n,d,s)^{O(\log \log (ds))}$$, where $$d = \max_{i\in [s]}d_i$$. Of course, it is conjectured that polynomial identity testing can be solved in deterministic polynomial time, so this is unlikely to be the best possible deterministic algorithm for this problem.
The best-known algorithm for testing isomorphism of finite groups whose solvable radical is either (a) contained in the center or (b) elementary abelian, is $$n^{O(\log \log n)}$$. These are, respectively, Theorems A and B of my paper with Youming Qiao. In this case, the bound comes from enumerating the automorphisms of $$G/Rad(G)$$, which is a group with no abelian normal subgroups (aka Fitting-free or semisimple). The number of such automorphisms can indeed be as large as $$n^{\Theta(\log \log n)}$$ (e.g. if $$G/Rad(G) \cong A_5^k$$ where $$k = \Theta(\log |G|)$$). Improving this upper bound to $$n^{o(\log \log n)}$$ thus requires a new strategy (my guess would be that it's doable though).