[HN Gopher] A new, faster algorithm for the group isomorphism pr...
___________________________________________________________________
A new, faster algorithm for the group isomorphism problem
Author : theafh
Score : 88 points
Date : 2023-06-23 13:46 UTC (9 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| kjhughes wrote:
| 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 wrote:
| 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 wrote:
| I've wished for a long time that mathematicians would bring
| back the notation "ld" (logarithmus dualis), which I find
| very elegant, for log2. 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_ wrote:
| Name's new to me.
|
| https://en.wikipedia.org/wiki/Binary_logarithm
| klyrs wrote:
| 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
|
| 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 wrote:
| This is a power of a logarithm though? Whereas you're talking
| about the base and its argument.
| klyrs wrote:
| No, Strassen's isn't an exact match in this case. Just an
| example how strange exponents can crop up in complexity
| analysis. I was aiming to satisfy the original comment's
| ask for "intuition" rather than "read the entire paper and
| digest it in time to make an unassailable ELI5 while
| waiting for the bus."
| gilleain wrote:
| "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.
| boxfire wrote:
| Scroll scroll scroll and...
|
| https://arxiv.org/abs/2303.15412
| matthewdgreen wrote:
| > 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.
| bluepod4 wrote:
| 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.
| ouid wrote:
| [dead]
| samsquire wrote:
| Could this be used for computer program equivalence?
| ouid wrote:
| [dead]
| henrydark wrote:
| 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 wrote:
| 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).
___________________________________________________________________
(page generated 2023-06-23 23:01 UTC)