×

Quotient tests and random walks in computational group theory. (English) Zbl 1106.20026

Grigorchuk, Rostislav (ed.) et al., Topological and asymptotic aspects of group theory. AMS special session on probabilistic and asymptotic aspects of group theory, Athens, OH, USA, March 26–27, 2004 and the AMS special session on topological aspects of group theory, Nashville, TN, USA, October 16–17, 2004. Providence, RI: American Mathematical Society (AMS) (ISBN 0-8218-3756-7/pbk). Contemporary Mathematics 394, 31-45 (2006).
Summary: For many decision problems on a finitely presented group \(G\), we can quickly weed out negative solutions by using much quicker algorithms on an appropriately chosen quotient group \(G/K\) of \(G\). However, the behavior of such “quotient tests” can be sometimes paradoxical. In this paper, we analyze a few simple case studies of quotient tests for the classical identity, word, conjugacy problems in groups. We attempt to combine a rigorous analytic study with the assessment of algorithms from the practical point of view. It appears that, in case of finite quotient groups \(G/K\), the efficiency of the quotient test very much depends on the mixing times for random walks on the Cayley graph of \(G/K\).
For the entire collection see [Zbl 1085.20501].

MSC:

20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20F05 Generators, relations, and presentations of groups
20P05 Probabilistic methods in group theory
60G50 Sums of independent random variables; random walks
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite