Lune

FOCS2024Top-tier venue

Verifying Groups in Linear Time

Shai Evra, Shay Gadot, Ohad Klein, Ilan Komargodski

Abstract

Consider the following problem: Given annn×nnmultiplication table, decide whether it is a Cayley multiplication table of a group. Among deterministic algorithms for this problem, the best known algorithm is implied by F. W. Light's associativity test (1949) and has running time ofO(n2log⁡n){O}(n^{2}\log n). Allowing randomization. the best known algorithm has running time ofO(n2log⁡(1/δ))O(n^{2}\log(1/\delta)), whereδ>0\delta > 0is the error probability of the algorithm (Rajagopalan and Schulman, FOCS 1996, SICOMP 2000). In this work, we improve upon both of the above known algorithms. Specifically, we present a deterministic algorithm for the above problem whose running time isO(n2)O(n^{2}). This performance is optimal up to constants. A central tool we develop is an efficient algorithm for finding a subsetAAof a groupGGsatisfyingA2=GA^{2}=Gwhile∣A∣=O(∣G∣)\vert A\vert=O(\sqrt{\vert G\vert }).

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression DetectionBartlomiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin et al.STOC 2026 · 1 citation

Related papers

  1. Group isomorphism is nearly-linear time for most ordersHeiko Dietrich, James B. WilsonFOCS 2021 · 11 citations
  2. The Minimal Faithful Permutation Degree of Groups without Abelian Normal SubgroupsBireswar Das, Dhara ThakkarSTOC 2024 · 2 citations
  3. Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝Xiaorui SunSTOC 2023 · 6 citations
  4. On Deterministically Finding an Element of High Order Modulo a CompositeZiv Oznovich, Ben Lee VolkSODA 2026 · 1 citation
  5. Faster Algorithms for Bounded-Difference Min-Plus ProductShucheng Chi, Ran Duan, Tianle XieSODA 2022 · 5 citations
Dusk over the sea between two cliffs drawn in fine vertical lines