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?


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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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