-1

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?

Turbo
  • 12,812
  • 1
  • 19
  • 68

1 Answers1

2

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.

Robert Andrews
  • 743
  • 5
  • 10