<p>The best-known deterministic algorithm for testing polynomial identities given by depth-three diagonal circuits has running time <span class="math-container">$n^{O(\log \log n)}$</span> [1].</p>
<p>More explicitly, we are given an expression of the form <span class="math-container">$$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}$$</span> and we want to test if <span class="math-container">$f(x_1,\ldots,x_n)$</span> is the identically zero polynomial. Forbes, Shpilka, and Saptharishi gave a deterministic algorithm for this problem that runs in time <span class="math-container">$\mathsf{poly}(n,d,s)^{O(\log \log (ds))}$</span>, where <span class="math-container">$d = \max_{i\in [s]}d_i$</span>. 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.</p>
<p>[1] <em>Forbes, Michael A.; Saptharishi, Ramprasad; Shpilka, Amir</em>, <a href="http://dx.doi.org/10.1145/2591796.2591816" rel="noreferrer"><strong>Hitting sets for multilinear read-once algebraic branching programs, in any order</strong></a>, Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 867-875 (2014). <a href="https://zbmath.org/?q=an:1315.68127" rel="noreferrer">ZBL1315.68127</a>.</p>

CC BY-SA 4.0
2022-06-23T21:26:23.327Z
2022-06-23T21:26:23.327Z
Robert Andrews
<p>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 <span class="math-container">$n^{O(\log \log n)}$</span>. These are, respectively, Theorems A and B of my <a href="https://doi.org/10.1137/15M1009767" rel="noreferrer">paper with Youming Qiao</a>. In this case, the bound comes from enumerating the automorphisms of <span class="math-container">$G/Rad(G)$</span>, 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 <span class="math-container">$n^{\Theta(\log \log n)}$</span> (e.g. if <span class="math-container">$G/Rad(G) \cong A_5^k$</span> where <span class="math-container">$k = \Theta(\log |G|)$</span>). Improving this upper bound to <span class="math-container">$n^{o(\log \log n)}$</span> thus requires a new strategy (my guess would be that it's doable though).</p>

CC BY-SA 4.0
2022-06-23T21:54:41.950Z
2022-06-23T21:54:41.950Z
Joshua Grochow
<p>Probably not as interesting or natural such as the problems mentioned in the previous answers, another problem that would fit in your question in the one of finding a clique of size <span class="math-container">$\log\log n$</span> in a graph with <span class="math-container">$n$</span> vertices. And I believe that, under some standard <a href="https://en.wikipedia.org/wiki/Clique_problem#Fixed-parameter_intractability" rel="nofollow noreferrer">parameterized complexity assumptions</a>, this cannot be improved.</p>

CC BY-SA 4.0
2022-07-19T06:31:07.340Z
This answer is not incorrect, but to me choosing a parameter in a parameterized problem (here, the clique size) to get the time bound you want feels like cheating.
David Eppstein
CC BY-SA 4.0
2022-07-19T13:15:20.807Z
For sure! That's why I said it was not that natural. But perhaps it is still useful for the OP.
Vinicius dos Santos
CC BY-SA 4.0
2022-07-18T03:40:36.343Z
2022-07-18T03:40:36.343Z
Vinicius dos Santos
<p>It’s well known that problems such as integer factorization have running times contained in <span class="math-container">$e^{\text{Poly} \log }$</span> which is the same <span class="math-container">$n^{ \text{Poly} \log }$</span> (actually the log term is itself in a cube root for integer factorization)</p>
<p>So this got me wondering about complexity classes that live between polynomial time and <span class="math-container">$e^{\text{Poly} \log }$</span> namely <span class="math-container">$e^{\log \cdot \text{Poly} \log \log }$</span> or <span class="math-container">$n^{\text{Poly} \log \log}$</span> as the title puts it.</p>
<p>Are there any problems whose best known algorithms live in this runtime complexity?</p>

CC BY-SA 4.0
2022-06-21T11:08:40.767Z
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”).
Emil Jeřábek
CC BY-SA 4.0
2022-06-21T11:25:46.393Z
My apologies I made the mistake of n in my polylog statement being the number and not the input size
Sidharth Ghoshal
CC BY-SA 4.0
2022-06-21T11:27:48.870Z
See the notation here: https://en.m.wikipedia.org/wiki/Integer_factorization#Difficulty-and-complexity in section “current state of the art”
Sidharth Ghoshal
CC BY-SA 4.0
2022-06-21T11:30:24.977Z
Yes, the wikipedia article misleadingly uses $n$ for the number itself rather than the length of the input.
Emil Jeřábek
CC BY-SA 4.0
2022-06-23T12:20:25.897Z
What about how many primes numbers there up to n^(log(log(n))?
Shaq
<complexity-classes><time-complexity>
Are there any problems whose best known algorithms have running time $n^{\log \log n}$?
Sidharth Ghoshal
# Are there any problems whose best known algorithms have running time $n^{\log \log n}$?

(Asked by: username_0 on 2022-06-21)

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?

**Tags:** complexity-classes, time-complexity

> **Comments:**
> **username_1**: 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”).  
> **username_0**: My apologies I made the mistake of n in my polylog statement being the number and not the input size  
> **username_0**: See the notation here: https://en.m.wikipedia.org/wiki/Integer_factorization#Difficulty-and-complexity in section “current state of the art”  
> **username_1**: Yes, the wikipedia article misleadingly uses $n$ for the number itself rather than the length of the input.  
> **username_2**: What about how many primes numbers there up to n^(log(log(n))?  

---

## 3 answers

### Answer by username_3 on 2022-06-23. Score: 11

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.

[1] *Forbes, Michael A.; Saptharishi, Ramprasad; Shpilka, Amir*, [**Hitting sets for multilinear read-once algebraic branching programs, in any order**](http://dx.doi.org/10.1145/2591796.2591816), Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 867-875 (2014). [ZBL1315.68127](https://zbmath.org/?q=an:1315.68127).


---

### Answer by username_4 on 2022-06-23. Score: 9

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](https://doi.org/10.1137/15M1009767). 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).


---

### Answer by username_5 on 2022-07-18. Score: 1

Probably not as interesting or natural such as the problems mentioned in the previous answers, another problem that would fit in your question in the one of finding a clique of size $\log\log n$ in a graph with $n$ vertices. And I believe that, under some standard [parameterized complexity assumptions](https://en.wikipedia.org/wiki/Clique_problem#Fixed-parameter_intractability), this cannot be improved.

> **Comments:**
> **username_6**: This answer is not incorrect, but to me choosing a parameter in a parameterized problem (here, the clique size) to get the time bound you want feels like cheating.  
> **username_5**: For sure! That's why I said it was not that natural. But perhaps it is still useful for the OP.  

---

