Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
For more than 35 years, the fastest known method for integer multiplication has been the Schonhage-Strassen algorithm running in time O(n log n log log n). Under certain restrictive conditions, there is a corresponding Omega(n log n) lower bound. All this time, the prevailing conjecture has been that the complexity of an optimal integer multiplication algorithm is Theta(n log n). We take a major step towards closing the gap between the upper bound and the conjectured lower bound by presenting an algorithm running in time n log n2(O)(log* n). The running time bound holds for multitape Turing machines. The same bound is valid for the size of Boolean circuits.
Giovanni De Micheli, Heinz Riener, Siang-Yun Lee
Mika Tapani Göös, Gilbert Théodore Maystre