I think I'm misunderstanding something about the article. In what way is this method perfect, as is mentioned multiple times? Is it not just an incremental improvement over standard practice?
If you get the order down to the proven limit, especially for the first time, people sometimes use the word 'perfect', even if there are potentially other solutions with lower constant overhead, or lower practical overhead (see also Timsort, which uses insertion sort for leaf operations).
> Second, in that same paper Schönhage and Strassen conjectured that there should be an even faster algorithm than the one they found — a method that needs only n × log n single-digit operations — and that such an algorithm would be the fastest possible.
Is this saying that there is a proof in there paper that nlogn is the cheapest? If so it certainly beats around the bush.
> At the end of February, a team of computer scientists at Aarhus University posted a paper arguing that if another unproven conjecture is also true, this is indeed the fastest way multiplication can be done.
[edit]
According to the abstract of the paper referred to in the article (https://arxiv.org/abs/1902.10935) it rests on a "central conjecture in the area of network coding". Make of that what you will.
>In this work, we prove that if a central conjecture in the area of network coding is true, then any constant degree boolean circuit for multiplication must have size Ω(nlgn), thus almost completely settling the complexity of multiplication circuits
So, given an unproven assumption and also given that we are constrained to doing multiplication on a boolean circuit, this may be "perfect" in a sense.
Seems like the title is mostly just clickbait.
Conjectures aren't doing so hot in this area, it seems.
For that one counter-example how many conjectures turned out to be true?
> Harvey and van der Hoeven’s algorithm proves that multiplication can be done in n × log n steps. However, it doesn’t prove that there’s no faster way to do it. Establishing that this is the best possible approach is much more difficult. At the end of February, a team of computer scientists at Aarhus University posted a paper arguing that if another unproven conjecture is also true, this is indeed the fastest way multiplication can be done.
Even if the conjecture is proven to be true, we may find a more efficient way to perform this operation than a boolean circuit.