Multiplying integers

The classical algorithm, that everyone knows from elementary school, for multiplying two n-digit integers runs in \(O(n^2)\)-time.

Recently, there was a preprint posted on HAL (link) in which the authors provide an algorithm which runs in \(O(n\log(n))\)-time.

A nice article about this discovery may be found at the QuantaMagazine: link.

Further, it was also recently proven in another preprint (link) that \(O(n\log(n))\)-time is conditionally (i.e., if a certain conjecture in network coding is true) the best possible.

Update (May 7th): the results in the last linked preprint (link) are extremely strong and hence one should, at least for the time being, take it with a grain of salt (further information: link).