After millenia of quest we have identified two $n$ bit integers can be multiplied in $O(n\log n)$ time. Please refer details in https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/. The problem of placing multiplication in $O(n)$ time is still unsolved.

  1. What evidence do we have that this can/cannot be brought to $O(n)$ time on uniform Turning model?

  2. What evidence do we have that this can/cannot be brought to $O(n)$ complexity in a reasonable non-uniform model?


1 Answer 1


In regards to (2), conditional super-linear lower bounds are known. A recent preprint by Afshani, Freksen, Kamma, and Larsen proves an $\Omega(n \log n)$ lower bound for the size of Boolean circuits computing integer multiplication, assuming a certain conjecture on network coding in undirected graphs. (See also this blog post and a follow-up post.)

From the linked post on major unsolved problems, a super-linear lower bound follows from the Heartmanis-Stearns conjecture.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.