Local expansion of vertex-transitive graphs and random generation in finite groups

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Local expansion of vertex-transitive graphs and random generation in finite groups

Full text

Pdf (1.16 MB)

Source

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

New Orleans, Louisiana, United States

Pages: 164 - 174

Year of Publication: 1991

ISBN:0-89791-397-3

Author

László Babai

Univ. of Chicago, Chicago, IL

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 50, Citation Count: 19

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

	Ald	D. Aldous: On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing, Probability in Engineering and Informational Sciences I (1987), 33-46.
	Alo	N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
	Ba1	L. Babai: Monte Carlo algorithms in graph isomorphism testing, Universit@ de Montreal Tech. Pep. DMS 79-10, 1979.
	Ba2	L Babai, Trading group theory for randomness, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.421-429, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22192]
	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. Bahai: Computational complexity in finite groups, Proc. International Congress of Mathematicians, Kyoto 1990, Springer, to appear
	BCFS	L. Babai, G. Cooperman, L. Finkelstein,/k. Seress: Permutation groups with small base in almost linear time, manuscript 1990
	BCFLS	László Babai , Gene Cooperman , Larry Finkelstein , Eugene Luks , Ákos Seress, Fast Monte Carlo algorithms for permutation groups, Selected papers of the 23rd annual ACM symposium on Theory of computing, p.296-308, April 1995, New Orleans, Louisiana, United States
	BE	L. Babai, P. Erd6s: Representation of group elements as short products, in: Theory and Practice of Combinatorics (A. Rosa et al., eds.), Ann. Discr. Math. 12 (1982), 27-30.
	BLS	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]
	BSz	L. Babai, E. Szemer6di: On the complexity of matrix group problems i, in: Proc. 25th IEEE FOCS, 1984, pp. 229-240.
	Ca	R. Carter: Simple groups of Lie type, Wiley 1972, 1989.
	Ch	J. Cheeger: A lower bound for the smallest eigenvalue of the Laplacian, in: Problems in AnMysis, Princeton Univ. Press 1970, pp. 195-199.
	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]
	Di	P. Diaconis: Group Representations in Probability and Statistics, Inst. Math. Stat. Hayward CA 1988.
	ER	P. Erd6s, A. R4nyi" Probabilistic methods in group theory, J. d'Analyse Math. 14 (1965), 127-138.
	GMR	S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
	FHL	M.L.Furst,J.Hopcroft, E. M. Luks: Polynomial-time algorithms for permutation groups, in: 21st IEEE FOCS, 1980, pp. 36-41.
	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]
	JVV	M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
	KL	W. M. Kantor , E. M. Luks, Computing in quotient groups, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.524-534, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100290]
	Kn	D. E. Knuth: Efficient representation of perm groups, Combinatorica, to appear
	MW	B. Mohar, W. Woess: A survey on spectra of infinite graphs, Bull. London Math. Soc. 21 (1989), 209-234.
	NP	P. M. Neumann, Cheryl E. Praeger: A recognition algorithm for the special linear groups, 1990.
	Ré	A. R#nyi: Selected Papers (P. Tur~n, ed.), Akad@miai Kiad6, Budapest, 1976.
	Sim	C. C. Sims, Some group theoretic algorithms, in" Lecture Notes in Math. 697 (1978), pp. 108-124.
	Sze	M. Szegedy, Notes on the expansion property of symmetric graphs, in preparation
	SJ	Alistair Sinclair , Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, v.82 n.1, p.93-133, July 1989 [doi>10.1016/0890-5401(89)90067-9]
	Va	N. Th. Varopoulos: Isoperimetric inequalities and Markov chains, J. Funct. AnM. 63 (1985), 215-239.

CITED BY 19

	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 , Katalin Friedl , Markus Stricker, Decomposition of *-closed algebras in polynomial time, Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.86-94, July 06-08, 1993, Kiev, Ukraine
	Igor Pak , Sergey Bratus, On sampling generating sets of finite groups and product replacement algorithm: extended abstract, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.91-96, July 28-31, 1999, Vancouver, British Columbia, Canada
	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
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Gene Cooperman , Larry Finkelstein , Bryant York , Michael Tselman, Constructing permutation representations for large matrix groups, Proceedings of the international symposium on Symbolic and algebraic computation, p.134-138, July 20-22, 1994, Oxford, United Kingdom
	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
	László Babai , Gene Cooperman , Larry Finkelstein , Ákos Seress, Nearly linear time algorithms for permutation groups with a small base, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.200-209, July 15-17, 1991, Bonn, West Germany
	László Babai , Robert Beals , Daniel Rockmore, Deciding finiteness of matrix groups in deterministic polynomial time, Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.117-126, July 06-08, 1993, Kiev, Ukraine
	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, 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
	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
	Peter A. Brooksbank, Constructive recognition of classical groups in their natural representation, Journal of Symbolic Computation, v.35 n.2, p.195-239, February 2003
	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
	John Watrous, Quantum algorithms for solvable groups, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.60-67, July 2001, Hersonissos, Greece
	László Babai, On the diameter of Eulerian orientations of graphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.822-831, January 22-26, 2006, Miami, Florida
	András Lukács, Generating random elements of abelian groups, Random Structures & Algorithms, v.26 n.4, p.437-445, July 2005
	András Lukács, On Local Expansion of Vertex-Transitive Graphs, Combinatorics, Probability and Computing, v.7 n.2, p.205-209, June 1998
	László Babai , Robert Beals , Ákos Seress, Polynomial-time theory of matrix groups, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA