Deciding finiteness of matrix groups in deterministic polynomial time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Deciding finiteness of matrix groups in deterministic polynomial time

Full text

Pdf (946 KB)

Source

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

Kiev, Ukraine

Pages: 117 - 126

Year of Publication: 1993

ISBN:0-89791-604-2

Authors

László Babai
Robert Beals
Daniel Rockmore

Sponsor

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: 4

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

	Alo	N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
	Ba1	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]
	Ba2	L. Bahai: Computational complexity in finite groups, in: Proc. International Congress of Mathematicians, Kyoto 1990, Springer, Hong Kong 1991, pp. 1479-1489.
	Ba3	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
	BF	László Babai , Katalin Fried, Approximate representation theory of finite groups, Proceedings of the 32nd annual symposium on Foundations of computer science, p.733-742, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185442]
	BR	L. Babai, L. R6nyai: Computing irreducible representations of finite groups, Math. Comp. 55 (1990), 705-722. (Preliminary version: 30th FOCS, 1989, pp. 93-98.)
	BSz	L. Babai, E. Szemer6di: On the complexity of matrix group problems i, in: Proc. 25th IEEE FOCS, Palm Beach FL, 1984, pp. 229-240.
	Bu	W. Burnside, Theory of Groups of Finite Order, 2nd ed., Cambridge, 1911.
	CR	C. W. Curtis, I. Reiner: Representation Theory of Finite Groups and Associative Algebras, Wiley, New York, 1966.
	Dic	L. E. Dickson: Algebras and Their Arithmetics, University of Chicago Press, Chicago, 1923.
	Dix	J. Dixon: Computing irreducible representations of groups, Math. Comp. 24 (1970), 446-450.
	Eb	Wayne Michael Eberly , J. Von Gathen, Computations for algebras and group representations, 1989
	ER	P. Erd6s, A. R~nyi: Probabilistic methods in group theory, J. d'Analyse Math. 14 (1965), 127- 138.
	FR	K Friedl , L Rónyai, Polynomial time solutions of some problems of computational algebra, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.153-162, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22162]
	GL	G. H. Golub, C. F. Van Loan: Matrix Computations, Johns Hopkins Univ. Press, Baltimore, 1989.
	GLS	M. GrStschel, L. Lov~sz, A. Schrijver: Geometric Algorithms and Combinatoriai Optimization, Springer-Verlag, Berlin, 1987.
	Ha	P. galmos: Finite-dimensionai Vector Spaces, Van Nostrand, Princeton, 1958.
	LLL	A. K. Lenstra, H. W. Lenstra, L. Lov~sz: Factoring Polynomials with Rational Coefficients, Math. Ann. 261 (1982), pp. 515-534.
	Mi	K. A. Mihailova: The occurrence problem for direct products of groups (in Russian), Dokl. Akad. Nauk SSSR 119 (1958), pp. 1103-1105, and Mat. Sb. (IV. S.) 70 (112) (1966), pp. 241-251.
	New	M. Newman: Integral Matrices, Pure and Applied Mathematics, vol. 45, Academic Press, New York, 1972.
	Ro1	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]
	Sp	A. Speiser: Die Theorie der Gruppen yon endlicher Ordnung, Dritte Auflage, Dover, NY, 1937.

CITED BY 4

	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
	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
	A. S. Detinko , D. L. Flannery, Algorithms for computing with nilpotent matrix groups over infinite domains, Journal of Symbolic Computation, v.43 n.1, p.8-26, January, 2008
	A. S. Detinko , D. L. Flannery, On deciding finiteness of matrix groups, Journal of Symbolic Computation, v.44 n.8, p.1037-1043, August, 2009