Testing commutativity of a group and the power of randomization

DOI10.1112/S1461157012000046zbMath1296.20068OpenAlexW2126586388WikidataQ56386243 ScholiaQ56386243MaRDI QIDQ5169624

Igor Pak

Publication date: 11 July 2014

Published in: LMS Journal of Computation and Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1112/s1461157012000046

zbMATH Keywords

deterministic algorithmsmatrix groupsrandomized algorithmsblack box groupscommutativity testsgroup multiplications

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear algebraic groups over finite fields (20G40) Generators, relations, and presentations of groups (20F05) Probabilistic methods in group theory (20P05)

Related Items (2)

Quantum Walk Based Search Algorithms ⋮ Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond

Cites Work

• Self-testing/correcting with applications to numerical problems
• An \(O(n)\) algorithm for Abelian \(p\)-group isomorphism and an \(O(n \log n)\) algorithm for Abelian group isomorphism
• Fast Monte Carlo algorithms for permutation groups
• Probabilistic methods in group theory
• Quantum complexity of testing group commutativity
• Linear time algorithms for Abelian group isomorphism and related problems
• The Probability of Generating a Finite Soluble Group
• Quantum Walk Based Search Algorithms
• How commutative can a non-commutative group be?

This page was built for publication: Testing commutativity of a group and the power of randomization