Computer Scientists Inch Closer to Major Algorithmic Goal | Quanta Magazine

Abstraction: New algorithm improves group isomorphism speed for hardest p-group class

Key points:

• Xiaorui Sun (UIC) presented a faster algorithm for the group isomorphism problem, posted March 2023, targeting p-groups of class 2 and exponent p — the hardest known subcase
• Previous best runtime was n^(log n) (Tarjan, 1970s); Sun achieves n^((log n)^(5/6)), a first improvement in ~50 years
• Method: uses Baer correspondence to translate groups into matrix spaces, then splits each space into a "core" (simple, handled analytically) and outer layer (complex, handled by individualization-and-refinement search)
• Group isomorphism reduces to graph isomorphism, so stalling on groups has blocked graph isomorphism progress
• Algorithm still sits between exponential and polynomial time; does not resolve which complexity class the problem falls into
• László Babai's 2015 quasi-polynomial graph isomorphism result is a benchmark context for this work

Connections: Computational Complexity · Graph Isomorphism · Algorithm Design

Source: https://www.quantamagazine.org/computer-scientists-inch-closer-to-major-algorithmic-goal-20230623/