Computing in quotient groups

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computing in quotient groups

Full text

Pdf (1.06 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents

Baltimore, Maryland, United States

Pages: 524 - 534

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

W. M. Kantor	University of Oregon
E. M. Luks	University of Oregon

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 31, Citation Count: 6

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/100216.100290 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	[Ba1] L. Babai, Monte Carlo algorithms for graph isomorphism testing, Tech. Rep. 79-10, Dép. Math. et Stat., Univ. de Montréal 1979.
	2	László Babai, Moderately Exponential Bound for Graph Isomorphism, Proceedings of the 1981 International FCT-Conference on Fundamentals of Computation Theory, p.34-50, August 24-28, 1981
	3	[Ba3] L. Babai, A Las Vegas-NC algorithm for isomorphism of graphs with bounded multiplicity of eigenvalues , Proc. 27th IEEE FOCS, 1986, 303-312.
	4	[Ba4] L. Babai, On the length of subgroup chains in the symmetric group, Comm. in Alg. 14 (1986), 1729- 1736.
	5	[BCP] L. Babai, P. Cameron and P.J. Pálfy, On the order of primitive groups with restricted nonabelian composition factors, J. Algebra 79 (1982), 161-168.
	6	[BK] L. Babai and L. Ku¿era, Canonical labelling of graphs in linear average time, Proc. 20th IEEE FOCS, 1979, 39-46.
	7	[BKL] L. Babai, W.M. Kantor and E.M. Luks, Computational complexity and the classification of finite simple groups, Proc. 24th IEEE FOCS, 1983, 162- 171.
	8	László Babai , Eugene M. Luks, Canonical labeling of graphs, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.171-183, December 1983 [doi>10.1145/800061.808746]
	9	L. Babai , E. Luks , A. Seress, Permutation groups in NC, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.409-420, January 1987, New York, New York, United States [doi>10.1145/28395.28439]
	10	[BLS2] L. Babai, E.M. Luks and Á. Seress, Fast management of permutation groups, Proc. 29th IEEE FOCS, 1988, 272-282.
	11	László Babai , Shlomo Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class, Journal of Computer and System Sciences, v.36 n.2, p.254-276, April 1988 [doi>10.1016/0022-0000(88)90028-1]
	12	[BS] L. Babai and E. Szemerédi, On the complexity of matrix group problems, Proc. 24th IEEE FOCS, 1984, 229-240.
	13	[Ca] J.J. Cannon, An introduction to the group theory language Cayley, in Computational Group Theory (ed. M.D. Atkinson), Academic Press 1984, 145- 183.
	14	G. Cooperman , L. Finkelstein , E. Luks, Reduction of group constructions to point stabilizers, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.351-356, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74581]
	15	[FHL] M.L. Furst, J. Hopcroft and E.M. Luks, Polynomial time algorithms for permutation groups, Proc. 21th IEEE FOCS, 1980, 36-41.
	16	Martin Fürer , Walter Schnyder , Ernst Specker, Normal forms for trivalent graphs and graphs of bounded valence, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.161-170, December 1983 [doi>10.1145/800061.808745]
	17	[GMW] O. Goldreich, S. Micali and A. Wigderson, Proofs that yield nothing but their validity and a methodology of cryptographic protocol design, Proc. 27th IEEE FOCS, 1986, 174-187.
	18	[Go] D. Gorenstein, Finite Groups. Harper and Row, New York 1968.
	19	[Ha] M. Hall, Jr., The Theory of Groups, Macmillan, New York 1959.
	20	[Ho] C.M. Hoffmann, Group Theoretic Algorithms and Graph Isomorphism, Lect. Notes in Comp. Sci. 136, Springer 1982.
	21	[Ka1] W.M. Kantor, Polynomial-time algorithms for finding elements of prime order and Sylow subgroups, J. Algorithms 6 (1985) 478-514.
	22	[Ka2] W.M. Kantor, Sylow's theorem in polynomial time, J. Comp. Syst. Sci. 30 (1985) 359-394.
	23	William M. Kantor, Finding Sylow normalizers in polynomial time, Journal of Algorithms, v.11 n.4, p.523-563, Dec. 1990 [doi>10.1016/0196-6774(90)90009-4]
	24	[KL] W.M. Kantor and E.M. Luks, Algorithms for quotients of permutation groups, in preparation.
	25	[Ku] L. Ku¿era, Canonical labeling of regular graphs in linear average time, Proc. 28th IEEE FOCS 1987, 271-279.
	26	W. M. Kantor , D. E. Taylor, Polynomial-time versions of Sylow's theorem, Journal of Algorithms, v.9 n.1, p.1-17, March 1988 [doi>10.1016/0196-6774(88)90002-8]
	27	[Le] J.S. Leon, On an algorithm for finding a base and strong generating set for a group given by generating permutations, Math. Comp. 35 (1980), 941-974.
	28	[Lu1] E.M. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Comp. Syst. Sci. 25 (1982), 42-65.
	29	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]
	30	[McK] B, McKay, nauty User's Guide (version 1.2), Tech. Rep. TR-CS-87-03, Dept. Comp. Sci., Austral. Nat. Univ. 1987.
	31	[Mi1] G.L. Miller, Isomorphism of k-contractible graphs, a generalization of bounded valence and bounded genus, Inform. and Control 56, 1983, 1-20.
	32	[Mi2] G.L. Miller, Isomorphism of graphs which are pairwise k-separable, Inform. and Control 56, 1983, 21- 33.
	33	[Ne] P.M. Neumann, Some algorithms for computing with finite permutation groups, Proc. of Groups-St. Andrews 1985 (Eds. E.F. Robertson and C.M. Campbell), London Math. Soc. Lect. Note 121, Cambridge U. Press 1987, 59-92.
	34	Lajos Rónyai, Computing the structure of finite algebras, Journal of Symbolic Computation, v.9 n.3, p.355-373, March 1990 [doi>10.1016/S0747-7171(08)80017-X]
	35	[Si] C.C. Sims, Some group-theoretic algorithms, Springer Lect. Notes in Math. 697 (1978), 108-124.
	36	[Wi] H. Wielandt, Finite Permutation Groups, Acad. Press, N.Y. 1964.

CITED BY 6

	Eugene M. Luks , Takunari Miyazaki, Polynomial-time normalizers for permutation groups with restricted composition factors, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.176-183, July 07-10, 2002, Lille, France
	Eugene M. Luks , Ferenc Rákóczi , Charles R. B. Wright, Computing normalizers in permutation p-groups, Proceedings of the international symposium on Symbolic and algebraic computation, p.139-146, July 20-22, 1994, Oxford, United Kingdom
	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
	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
	Alexander Hulpke, Computing normal subgroups, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.194-198, August 13-15, 1998, Rostock, Germany
	John J. Cannon , Derek F. Holt, Automorphism group computation and isomorphism testing in finite groups, Journal of Symbolic Computation, v.35 n.3, p.241-267, March 2003