3 ms·
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.
by dogfoods 6y ago
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.
- senkora 6y agoThey 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.
- mumbisChungo 6y agoYes, 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.