Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T15:00:18.417Z Has data issue: false hasContentIssue false

Testing commutativity of a group and the power of randomization

Published online by Cambridge University Press:  01 April 2012

Igor Pak*
Affiliation:
Department of Mathematics, University of California, Los Angeles, 530 Portola Plazza 6363 Math Sciences Building Los Angeles, CA 90095-1555, USA (email: pak@math.ucla.edu)

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let G be a group generated by k elements, G=〈g1,…,gk〉, with group operations (multiplication, inversion and comparison with identity) performed by a black box. We prove that one can test whether the group G is abelian at a cost of O(k) group operations. On the other hand, we show that a deterministic approach requires Ω(k2) group operations.

Information

Type
Research Article
Copyright
Copyright © London Mathematical Society 2012