Re:Mathematicians discover a perfect way to multiply (2019)
by dogfoods on Wednesday July 22, 2020 @03:26PM
(#23920616)
It achieves a theoretical lower bound on the complexity. This is what the article says in like 1000 words because it's written for mathematical illiterates.
[ Parent
| on HN ]
Re:Mathematicians discover a perfect way to multiply (2019)
by senkora on Wednesday July 22, 2020 @03:33PM
(#23920681)
They do not prove a lower bound.
> 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.
Re:Mathematicians discover a perfect way to multiply (2019)
by mumbisChungo on Wednesday July 22, 2020 @03:33PM
(#23920685)
Yes, a lower bound for multiplication using a boolean circuit, resting on an unproven conjecture.
Even if the conjecture is proven to be true, we may find a more efficient way to perform this operation than a boolean circuit.