On sampling generating sets of finite groups and product replacement algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On sampling generating sets of finite groups and product replacement algorithm: extended abstract

Full text

Pdf (690 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 1999 international symposium on Symbolic and algebraic computation table of contents

Vancouver, British Columbia, Canada

Pages: 91 - 96

Year of Publication: 1999

ISBN:1-58113-073-2

Authors

Igor Pak	Department of Mathematics, Yale University, New Haven, CT
Sergey Bratus	Department of Mathematics, Northeastern University, Boston, MA

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 16, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/309831.309871 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	ALDOUS, D., AND DIACONIS, P. Schuffling cards and stopping times. Amer. Math. Monthly 93, 5 (1986), 333-348.
	2	ALDOUS, D., AND FILL, J. Reversible markov chains and random walks on graphs. monograph in preparation, 1996.
	3	ALON, N., AND ROICHMAN, Y. Random Cayley graphs and expanders. Random Structures Algorithms 5, 2 (1994), 271 284.
	4	László Babai, Local expansion of vertex-transitive graphs and random generation in finite groups, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.164-174, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103440]
	5	László Babai, Automorphism groups, isomorphism, reconstruction, Handbook of combinatorics (vol. 2), MIT Press, Cambridge, MA, 1996
	6	BABAI, L. Randomization in group algorithms: conceptual questions. In Groups and computation, II (New Brunswick, NJ, 1995). Amer. Math. Soc., Providence, RI, 1997, pp. 1 17.
	7	BEALS, R., AND BABAI, L. Las Vegas algorithms for matrix groups. In 34th Annual Symposium on Foundations of Computer Science (Palo Alto, CA, 1993). IEEE Comput. Soc. Press, Los Alamitos, CA, 1993, pp. 427-436.
	8	BRATUS, S., COOPERMAN, G., FINKELSTEIN, L., AND LINTON, S. Constructive recognition of a black box group isomorphic to GL(n,q). monograph in preparation, 1998.
	9	BRATUS, S., AND PAK, I. Fast constructive recognition of a black box group isomorphic to Sn or An. preprint, 1997.
	10	CELLER, F., AND LEEDIIAM-GREEN, C. R. A nonconstructive recognition algorithm for the special linear and other classical groups. In Groups and computation, II (New Brunswick, NJ, 1995). Amer. Math. Soc., Providence, RI, 1997, pp. 61-67.
	11	CELLER, F.. LEEDHAM-GREEN, C. R., MURRAY, S. H., NIEMEYER, A. C., AND O'BRIEN, E. A. Generating random elements of a finite group. Comm. Algebra 23, 13 (1995), 4931-1948.
	12	CHUNG, F. R. K., AND GRAHAM, R. L. Random walks on generating sets for finite groups. Electron. J. Combin. 4, 2 (1997), Research Paper 7, approx. 14 pp. (electronic). The Wilf Festschrift (Philadelphia, PA, 1996).
	13	COOPERMAN, G., AND FINKELSTEIN, L. Combinatorial tools for computational group theory. In Groups and computation (New Brunswick, NJ, 1991). Amer. Math. Soc., Providence, RI, 1993, pp. 53-86.
	14	COXETER, H. S. M., AND MOSER, W. O. J. Generators and relations for discrete groups, third ed. SpringerVerlag, New York, 1972. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 14.
	15	DIACONIS, P., AND GRAHAM, R. The graph of generating sets of an abelian group. to appear, 1997.
	16	DIACONIS, P., AND SALOFF-COSTE, L. Walks on generating sets of abelian groups. Probab. Theory Related Fields 105, 3 (1996), 393-421.
	17	DIACONIS, P., AND SALOFF-COSTE, L. Walks on generating sets of groups. Invent. Math. 134, 2 (1998), 251-299.
	18	DIXOX, J. D. The probability of generating the symmetric group. Math. Z. 110 (1969), 199 205.
	19	DOU, C., AND HILDEBRAND, M. Enumeration and random random walks on finite groups. Ann. Probab. 24, 2 (1996), 987 . 1000.
	20	DRD~S, P., aND R~NYI, A. Probabilistic methods in group theory. J. Analyse Math. 14 (1965), 127-138.
	21	GASCH~TZ, W. Die Eulersche Funktion Endlicher aufi~sbarer Gruppen. Illinois J. Math. 3 (1959), 469-476.
	22	HALL, MARSIIALL, J. The theory of groups. Chelsea Publishing Co., New York, 1976. Reprinting of the 1968 edition.
	23	HALL, P. The eulerian functions of a group. Quart. J. Math. 7 (1936), 134 151.
	24	KANTOR, W. M. Simple groups in computational group theory. In Proceedings of the International Congress of Mathematicians, Vol. II (Berlin, 1998) (1998), pp. 77-86 (electronic).
	25	KANTOR, W. M., AND LUBOTZKY, A. The probability of generating a finite classical group. Geom. Dedicata 36, 1 (1990), 67-87.
	26	KANTOR, W. M., AND SERESS, A. Black box classical groups. preprint, 1997.
	27	LIEBECK, M. W., AND SHALEV, A. The probability of generating a finite simple group. Geom. Dedicata 56, 1 (1995), 103 113.
	28	E. M. Luks, Computing the composition factors of a permutation group in polynomial time, Combinatorica, v.7 n.1, p.87-99, Jan. 1987 [doi>10.1007/BF02579204]
	29	LUKS, E. M. Computing in solvable matrix groups. In Proc. 33rd IEEE FOCS (1992), pp. 111-120.
	30	NEUMANN, P. M., AND PRAEGER, C. E. Cyclic matrices over finite fields. J. London Math. Soc. (2) 52, 2 (1995), 263-284.
	31	NIEMEYER, A. C., AND PRAEGER, kC. E. A recognition algorithm for classical groups over finite fields. Proc. London Math. Soc. (3) 77, 1 (1998), 117-169.
	32	PAK, I. When and how n chose k. In DIMACS Series, vol. 43. Amer. Math. Soc., Providence, RI, 1998, pp. 191-238.
	33	PAK, I. Random walks on finite groups with few random generators . Electron. J. Prob. 4 (1999). 1-11.
	34	PAK, I., AND VU, V. On finite jgeometric random walds. preprint, 1998.
	35	RANDALL, D. Effiecient generation of random nonsingular matrices. random Structures Algorithms 4, 1 (1993), 111 . 118.
	36	ROICIIMAN, Y. On random random walks. Ann. Probab. 24, 2 (1996), 1001-1011.
	37	SIIALEV, A. Probabilistic groups theory. St. Andrews Lectures, Bath. 1997.
	38	Charles C. Sims, Computation with permutation groups, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.23-28, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806264]
	39	WILSON, D. B. Random random walks on Zd2. Probab. Theory related Fields 108, 4 (1997), 441-457.

CITED BY 2

	László Babai , Igor Pak, Strong bias of group generators: an obstacle to the “product replacement algorithm”, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.627-635, January 09-11, 2000, San Francisco, California, United States
	László Babai , Igor Pak, Strong bias of group generators: an obstacle to the "product replacement algorithm", Journal of Algorithms, v.50 n.2, p.215-231, February 2004