Borovik, Alexandre V.; Myasnikov, Alexei G. 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]. Cited in 2 Documents 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 Keywords:decision problems; finitely presented groups; conjugacy problem; finite quotient groups; efficiency; quotient tests; random walks; Cayley graphs; identity problem; word problem; decision algorithms PDFBibTeX XMLCite \textit{A. V. Borovik} and \textit{A. G. Myasnikov}, Contemp. Math. 394, 31--45 (2006; Zbl 1106.20026)