9 ms·

A new, faster algorithm for the group isomorphism problem

110 points by theafh 3y ago

boxfire 3y ago
Scroll scroll scroll and... https://arxiv.org/abs/2303.15412 https://arxiv.org/abs/2303.15412
- matthewdgreen 3y ago
  > Scroll scroll scroll and... The new result (with explicit link to the arXiv as well as the author's home page) is linked in the fourth paragraph, and it only appears that far down because the first three paragraphs very efficiently provide background on the problem and recent results. The whole thing is an excellent general-audiences article explaining a complex theoretical result with illustrations and accessible links to all the relevant source material. I'm really glad we have Quanta and I'm not sure how this reporting could have been handled better.
  - ouid 3y ago
    [dead]
  - bluepod4 3y ago
    Exactly. EDIT: I was going to write a snark-ish comment that someone would eventually complain about the post title only to refresh a second later and see that someone changed the title already. “Major algorithmic goal” was completely fine and says quite a few different things than “new, faster”. Also, according to HN’s guidelines, the post title shouldn’t have changed in this situation: “Otherwise please use the original title, unless it is misleading or linkbait; don't editorialize.” The original title was not misleading or linkbait.
kjhughes 3y ago
The "major algorithmic goal" is better time complexity for group isomorphism. Xiaorui Sun improved on Robert Tarjan's (50-year-old) result, n^(log n) achieving n^((log n)^(5/6)) for certain types of groups that appear to be easier to compare but had been defying improvement attempts for decades. --- Anyone see intuitively how the 5 and 6 come into the improved complexity -- why those two particular constants?
- scythe 3y ago
  I can't say for "intuitive", but the introduction to the paper involves breaking p-groups — groups having p^k members where p is a prime — into the cases k > lg(p)^5 and k <= lg(p)^5, which likely explains why the number 5 has crashed the party. (Here lg() denotes the log base 2)
  - schoen 3y ago
    I've wished for a long time that mathematicians would bring back the notation "ld" (logarithmus dualis), which I find very elegant, for log₂. The "ln" is already from Latin (that's why it's ln instead of nl), I think established by Gauss or something.
    - _a_a_a_ 3y ago
      Name's new to me. https://en.wikipedia.org/wiki/Binary_logarithm https://en.wikipedia.org/wiki/Binary_logarithm
    - bmacho 3y ago
      But ld should denote the decimal logarithm. Binary logarithm should be denoted with lb.
- klyrs 3y ago
  Strassen's algorithm is, I think, one of the easier ones to understand along these lines. It uses a recursive divide and conquer strategy. The naive algorithm does 1 (N x N) multiplication by adding the results of 8 multiplications of size (N/2 x N/2), and (sweeping details under the rug here) that takes time N^log2(8) = N^3. The improved algorithm uses 7 multiplications of size (N/2 x N/2) and takes N^log2(7). For those details, the wiki page does a nice job. https://en.m.wikipedia.org/wiki/Strassen_algorithm https://en.m.wikipedia.org/wiki/Strassen_algorithm So intuitively speaking: when I see a logarithm like that with an integer ratio, I think "oh, somebody saved 1/6th of the work in a recursive algorithm."
  - dataflow 3y ago
samsquire 3y ago
Could this be used for computer program equivalence?
- ouid 3y ago
  [dead]
- henrydark 3y ago
  Don't think so, doesn't computer program equivalence require solving the halting problem and undecidable problems? For example, consider the empty program, and the program that print "hello, world!" if an undecidable condition is met. I think checking if these two programs are equivalent is undecidable
  - maweki 3y ago
    For these two programs it's easy to check that they are not equivalent. The magic words are "in general" and in general, program equivalence, as well as all other interesting program properties, are in general undecidable (Rice's Theorem).
gilleain 3y ago
"Sun's method takes an approach called individualization and refinement..." Which is what many standard methods for graph isomorphism use, if we are talking about the same thing.

110 points by theafh 3y ago

boxfire 3y ago

Scroll scroll scroll and... https://arxiv.org/abs/2303.15412 https://arxiv.org/abs/2303.15412

matthewdgreen 3y ago
> Scroll scroll scroll and... The new result (with explicit link to the arXiv as well as the author's home page) is linked in the fourth paragraph, and it only appears that far down because the first three paragraphs very efficiently provide background on the problem and recent results. The whole thing is an excellent general-audiences article explaining a complex theoretical result with illustrations and accessible links to all the relevant source material. I'm really glad we have Quanta and I'm not sure how this reporting could have been handled better.
- ouid 3y ago
  [dead]
- bluepod4 3y ago
  Exactly. EDIT: I was going to write a snark-ish comment that someone would eventually complain about the post title only to refresh a second later and see that someone changed the title already. “Major algorithmic goal” was completely fine and says quite a few different things than “new, faster”. Also, according to HN’s guidelines, the post title shouldn’t have changed in this situation: “Otherwise please use the original title, unless it is misleading or linkbait; don't editorialize.” The original title was not misleading or linkbait.

kjhughes 3y ago

The "major algorithmic goal" is better time complexity for group isomorphism. Xiaorui Sun improved on Robert Tarjan's (50-year-old) result, n^(log n) achieving n^((log n)^(5/6)) for certain types of groups that appear to be easier to compare but had been defying improvement attempts for decades. --- Anyone see intuitively how the 5 and 6 come into the improved complexity -- why those two particular constants?

scythe 3y ago
I can't say for "intuitive", but the introduction to the paper involves breaking p-groups — groups having p^k members where p is a prime — into the cases k > lg(p)^5 and k <= lg(p)^5, which likely explains why the number 5 has crashed the party. (Here lg() denotes the log base 2)
- schoen 3y ago
  I've wished for a long time that mathematicians would bring back the notation "ld" (logarithmus dualis), which I find very elegant, for log₂. The "ln" is already from Latin (that's why it's ln instead of nl), I think established by Gauss or something.
  - _a_a_a_ 3y ago
    Name's new to me. https://en.wikipedia.org/wiki/Binary_logarithm https://en.wikipedia.org/wiki/Binary_logarithm
  - bmacho 3y ago
    But ld should denote the decimal logarithm. Binary logarithm should be denoted with lb.
klyrs 3y ago
Strassen's algorithm is, I think, one of the easier ones to understand along these lines. It uses a recursive divide and conquer strategy. The naive algorithm does 1 (N x N) multiplication by adding the results of 8 multiplications of size (N/2 x N/2), and (sweeping details under the rug here) that takes time N^log2(8) = N^3. The improved algorithm uses 7 multiplications of size (N/2 x N/2) and takes N^log2(7). For those details, the wiki page does a nice job. https://en.m.wikipedia.org/wiki/Strassen_algorithm https://en.m.wikipedia.org/wiki/Strassen_algorithm So intuitively speaking: when I see a logarithm like that with an integer ratio, I think "oh, somebody saved 1/6th of the work in a recursive algorithm."
- dataflow 3y ago

samsquire 3y ago

Could this be used for computer program equivalence?

ouid 3y ago
[dead]
henrydark 3y ago
Don't think so, doesn't computer program equivalence require solving the halting problem and undecidable problems? For example, consider the empty program, and the program that print "hello, world!" if an undecidable condition is met. I think checking if these two programs are equivalent is undecidable
- maweki 3y ago
  For these two programs it's easy to check that they are not equivalent. The magic words are "in general" and in general, program equivalence, as well as all other interesting program properties, are in general undecidable (Rice's Theorem).

gilleain 3y ago

"Sun's method takes an approach called individualization and refinement..." Which is what many standard methods for graph isomorphism use, if we are talking about the same thing.