Nearly linear time algorithms for permutation groups with a small base

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Nearly linear time algorithms for permutation groups with a small base

Full text

Pdf (1.19 MB)

Source

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

Bonn, West Germany

Pages: 200 - 209

Year of Publication: 1991

ISBN:0-89791-437-6

Authors

László Babai	Dept. of Comp. Science, University of Chicago, Chicago, Illinois and Dept. of Algebra, Eötvös University, Budapest, Hungary H-1088
Gene Cooperman	College of Comp. Science, Northeastern University, Boston, Mass.
Larry Finkelstein	College of Comp. Science, Northeastern University, Boston, Mass.
Ákos Seress	Dept. of Mathematics, Ohio State University, Columbus, Ohio

Sponsors

GMD : German Natl Research Ctr for Information Tech. - Gesellschft
German Comp Soc : GI - Gesellshaft for Informatik
SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 18, Citation Count: 11

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/120694.120724 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.

	Ba1	L. Babai, "Monte-Carlo Algorithms in Graph Isomorphism Testing", Universit~ de Montreal Tech. Report D.M.S. 79-10 (1979), Dep. Math. et Stat.
	Ba2	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]
	Ba3	László Babai, Bounded round interactive proofs in finite groups, SIAM Journal on Discrete Mathematics, v.5 n.1, p.88-111, Feb. 1992 [doi>10.1137/0405008]
	Ba4	L. Babai, "Complexity in Finite Groups", Proc. International Congress of Mathematicians, Kyoto, 1990, Springer-Verlag, to appear.
	BCFLS	László Babai , Gene Cooperman , Larry Finkelstein , Eugene Luks , Ákos Seress, Fast Monte Carlo algorithms for permutation groups, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.90-100, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103435]
	BLS	L. Babai, E. Luks, and/~. Seress, "Fast Management of Permutation Groups", Proc. ~9th IEEE FOCS (1988), pp. 272-282.
	BSz	L. Babai and E. Szemer~di, "On the Complexity of Matrix Group Problems I," Proc. $5th IEEE FOCS (1984), Palm Beach, FL, pp. 229-240.
	Bl	K. Blaha, "The Greedy Algorithm and Bases for Permutation Groups", J. Algorithms, to appear.
	BFP	C. A. Brown , L. Finkelstein , P. W. Purdom, Jr., A new base change algorithm for permutation groups, SIAM Journal on Computing, v.18 n.5, p.1037-1047, Oct. 1989 [doi>10.1137/0218070]
	Ca	P.J. Cameron, "Finite Permutation Groups and Finite Simple Groups", Bull. London Math. Soc., 13, 1981, pp+ 1-22.
	Ch	H. Chernoff, "A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations", Ann. Math. Star. 23, (1952), pp. 493-507.
	Co	J.H. Conway et al., Atlas o} Finite Groups, Clarendon Press, Oxford, 1985.
	CF	Gene Cooperman , Larry Finkelstein, A strong generating test and short presentations for permutation groups, Journal of Symbolic Computation, v.12 n.4-5, p.475-497, Oct./Nov. 1991 [doi>10.1016/S0747-7171(08)80099-5]
	CFS	G. Cooperman , L. Finkelstein , N. Sarawagi, A random base change algorithm for permutation groups, Proceedings of the international symposium on Symbolic and algebraic computation, p.161-168, August 20-24, 1990, Tokyo, Japan [doi>10.1145/96877.96918]
	FHL	M. Purst, J. Hopcroft and E. Luks, "Polynomial Time Algorithms For Permutation Groups", Proc. ~1st IEEE FOCS (1980), pp. 36-41.
	Ha	M. Hall, Jr., The Theory o} Groups, Macmillan, New York, 1959.
	Je	Mark Jerrum, A compact representation for permutation groups, Journal of Algorithms, v.7 n.1, p.60-78, March 1986 [doi>10.1016/0196-6774(86)90038-6]
	Ka	W.M. Kantor, "Permutation Representations of the Finite Classical Groups of Small Degree or Rank", 2. Algebra 60 (1979), pp. 158-168.
	Kn	D.E. Knuth, "Notes on Efficient Representation of Perm Groups" Combinatorica 11 (199t), pp. 57-68 (preliminary version circulated since 1981).
	Si	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]

CITED BY 11

	Robert Beals, An elementary algorithm for computing the composition factors of a permutation group, Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.127-134, July 06-08, 1993, Kiev, Ukraine
	Gene Cooperman , Larry Finkelstein, A fast cyclic base change for permutation groups, Papers from the international symposium on Symbolic and algebraic computation, p.224-232, July 27-29, 1992, Berkeley, California, United States
	Robert Beals , Ákos Seress, Structure forest and composition factors for small base groups in nearly linear time, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.116-125, May 04-06, 1992, Victoria, British Columbia, Canada
	Martin Schönert , Ákos Seress, Finding blocks of imprimitivity in small-base groups in nearly linear time, Proceedings of the international symposium on Symbolic and algebraic computation, p.154-157, July 20-22, 1994, Oxford, United Kingdom
	Gene Cooperman , Larry Finkelstein , Michael Tselman, Computing with matrix groups using permutation representations, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.259-264, July 10-12, 1995, Montreal, Quebec, Canada
	Prabhav Marje, A nearly linear algorithm for Sylow subgroups in small-base groups, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.270-277, July 10-12, 1995, Montreal, Quebec, Canada
	László Babai, The growth rate of vertex-transitive planar graphs, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.564-573, January 05-07, 1997, New Orleans, Louisiana, United States
	László Babai, Deciding finiteness of matrix groups in Las Vegas polynomial time, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.33-40, September 1992, Orlando, Florida, United States
	Gene Cooperman , Eric Robinson, Memory-based and disk-based algorithms for very high degree permutation groups, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.66-73, August 03-06, 2003, Philadelphia, PA, USA
	Eric Robinson , Gene Cooperman, A parallel architecture for disk-based computing over the Baby Monster and other large finite simple groups, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	Max Neunhöffer , Ákos Seress, A data structure for a uniform approach to computations with finite groups, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy