Verifying Groups in Linear Time
Shai Evra, Shay Gadot, Ohad Klein, Ilan Komargodski
Abstract
Consider the following problem: Given an×multiplication 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 of. Allowing randomization. the best known algorithm has running time of, whereis 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 is. This performance is optimal up to constants. A central tool we develop is an efficient algorithm for finding a subsetof a groupsatisfyingwhile.
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.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers1
Related papers
- Group isomorphism is nearly-linear time for most ordersHeiko Dietrich, James B. WilsonFOCS 2021 · 11 citations
- The Minimal Faithful Permutation Degree of Groups without Abelian Normal SubgroupsBireswar Das, Dhara ThakkarSTOC 2024 · 2 citations
- Faster Isomorphism for 𝑝-Groups of Class 2 and Exponent 𝑝Xiaorui SunSTOC 2023 · 6 citations
- On Deterministically Finding an Element of High Order Modulo a CompositeZiv Oznovich, Ben Lee VolkSODA 2026 · 1 citation
- Faster Algorithms for Bounded-Difference Min-Plus ProductShucheng Chi, Ran Duan, Tianle XieSODA 2022 · 5 citations
