6 ms·

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 impr

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?

ogogmad 6y ago
It's perfect in the sense that its running time is O(n log n), and there is evidence that this is the fastest running time possible (at least up to a constant factor).
- mumbisChungo 6y ago
  And that evidence is... an unproven theory, which itself is also heavily qualified?
  - ogogmad 6y ago
    According to the article, it rests on a plausible conjecture. I need to read further. [edit] According to the abstract of the paper referred to in the article (https://arxiv.org/abs/1902.10935 https://arxiv.org/abs/1902.10935) it rests on a "central conjecture in the area of network coding". Make of that what you will.
    - mumbisChungo 6y ago
      From the abstract: >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.
    - hinkley 6y ago
      Yeah but in the backstory they also mentioned that Kolmogorov conjectured that the optimal solution was O(n^2). Conjectures aren't doing so hot in this area, it seems.
      - ChrisLomont 6y ago
        >Conjectures aren't doing so hot in this area, it seems. For that one counter-example how many conjectures turned out to be true?
        timwaagh 6y ago
        Ah but that's not what this game is about. It's about what you can prove. And conjectures are by definition things you can't prove yet. So the longer they stand and the more paths they block the more frustrating it gets.
  - dogfoods 6y ago
    RTFA and find out!
  - waynecochran 6y ago
    I would say most mathematical conjectures are stronger than most scientific theories. What I mean is that the conjectures are easily falsifiable (i.e., counter examples, if found, can easily be verified) and have been shown to be true for an enormous number of of cases. So unproven mathematical conjectures are not just "wild hypotheses."
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 ago
  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.
- mumbisChungo 6y ago
  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.
ghastmaster 6y ago
"Perfect" in this case is a qualitative exaggeration bordering on hyperbole. > 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 ago
  I would say it's firmly hyperbole/clickbait, upon further investigation.
  - bo1024 6y ago
    I think it’s fair. Nobody thinks a faster algorithm than n log n will ever be possible. It’s like a mini P!=NP.
    - effie 6y ago
      You don't know what nobody thinks, because there may be a person that thinks just that. This is an active area of research. Anything quicker than O(nlog n) but slower than O(n) is still possible.
hinkley 6y ago
In computational complexity, we have some proofs that a certain cost is the absolute bare minimum that an optimal solution must expend. We have the same for some mechanical systems too. 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.
- remcob 6y ago
  A conjecture is a proposition that is suspected to be true. So there would be no proof in the paper, but likely some arguments why the authors expect it to be true.
  - hinkley 6y ago
    If a scientist were writing the article about the paper, yes. But everyone has been quick to point out is definitely not the case.
- EvgeniyZh 6y ago
  There is a (conditional) proof that nlogn is optimal: https://arxiv.org/abs/1902.10935 https://arxiv.org/abs/1902.10935
- timwaagh 6y ago
  No (people think there isn't but it's not been proven).

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?

ogogmad 6y ago

It's perfect in the sense that its running time is O(n log n), and there is evidence that this is the fastest running time possible (at least up to a constant factor).

mumbisChungo 6y ago
And that evidence is... an unproven theory, which itself is also heavily qualified?
- ogogmad 6y ago
  According to the article, it rests on a plausible conjecture. I need to read further. [edit] According to the abstract of the paper referred to in the article (https://arxiv.org/abs/1902.10935 https://arxiv.org/abs/1902.10935) it rests on a "central conjecture in the area of network coding". Make of that what you will.
  - mumbisChungo 6y ago
    From the abstract: >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.
  - hinkley 6y ago
    Yeah but in the backstory they also mentioned that Kolmogorov conjectured that the optimal solution was O(n^2). Conjectures aren't doing so hot in this area, it seems.
    - ChrisLomont 6y ago
      >Conjectures aren't doing so hot in this area, it seems. For that one counter-example how many conjectures turned out to be true?
      - timwaagh 6y ago
        Ah but that's not what this game is about. It's about what you can prove. And conjectures are by definition things you can't prove yet. So the longer they stand and the more paths they block the more frustrating it gets.
- dogfoods 6y ago
  RTFA and find out!
- waynecochran 6y ago
  I would say most mathematical conjectures are stronger than most scientific theories. What I mean is that the conjectures are easily falsifiable (i.e., counter examples, if found, can easily be verified) and have been shown to be true for an enormous number of of cases. So unproven mathematical conjectures are not just "wild hypotheses."

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 ago
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.
mumbisChungo 6y ago
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.

ghastmaster 6y ago

"Perfect" in this case is a qualitative exaggeration bordering on hyperbole. > 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 ago
I would say it's firmly hyperbole/clickbait, upon further investigation.
- bo1024 6y ago
  I think it’s fair. Nobody thinks a faster algorithm than n log n will ever be possible. It’s like a mini P!=NP.
  - effie 6y ago
    You don't know what nobody thinks, because there may be a person that thinks just that. This is an active area of research. Anything quicker than O(nlog n) but slower than O(n) is still possible.

hinkley 6y ago

In computational complexity, we have some proofs that a certain cost is the absolute bare minimum that an optimal solution must expend. We have the same for some mechanical systems too. 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.

remcob 6y ago
A conjecture is a proposition that is suspected to be true. So there would be no proof in the paper, but likely some arguments why the authors expect it to be true.
- hinkley 6y ago
  If a scientist were writing the article about the paper, yes. But everyone has been quick to point out is definitely not the case.
EvgeniyZh 6y ago
There is a (conditional) proof that nlogn is optimal: https://arxiv.org/abs/1902.10935 https://arxiv.org/abs/1902.10935
timwaagh 6y ago
No (people think there isn't but it's not been proven).