Hacker News new | ask | show | jobs
by dogfoods 2164 days 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.
2 comments

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.

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.