Explicit expanders and the Ramanujan conjectures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Explicit expanders and the Ramanujan conjectures

Full text

Pdf (291 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 240 - 246

Year of Publication: 1986

ISBN:0-89791-193-8

Authors

A Lubotzky	Institute of Mathematics and Computer Science, Hebrew University, Jerusalem, Israel
R Phillips	Department of Mathematics, Stanford University, Stanford, California
P Sarnak	Department of Mathematics, Stanford University, Stanford, California

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 70, Citation Count: 24

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

	AKS	M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
	A	N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
	AGM	Alon, N., Galil, Z. and Milman, V.D., "Better expanders and superconcentrators", preprint 1984.
	AM	Alon, N. and Milman, V.D., "k isoperimetric inequalities for graphs and superconcentrators% J. Combin. Theory Ser. B38 (1985) 73-88.
	BP	Bassalygo, L.A. and Pinsker, M.S., "Complexity of an optimum nonblocking network without reconnections", Prob. Info. Trans. 9 (1974), 64-66.
	BA	Bassalygo, L.A., "Asymptotically optimal switching circuits", Problemy Peredachi Informatsii 17 (1981) 81-88.
	BU	Buck, M.W., "Expanders and diffusers", Preprint 1985.
	EI	Eichler, M.,"Quaternary forms and the Riemann hypothesis for congruence zeta functions", Archly der Math., Vol. 5 , 1954 (355-366).
	EGS	Erdos, P., Graham, R. and Szemer~di, E., "Sparse graphs with dense long paths", Computers and Math. with Appl., Vol. 1 (1975) 365-369.
	GG	Gabber, O. and Galil, Z., "Explicit constructions of linear-sized superconcentrators", J. Comput. System Sci. 22 (1981) 4O7-42O.
	GP	Gerritzer, L. and Van der Put, N., "Schottky groups and Mumford curves", Springer-Verlag Lecture Notes in Math. 817, Springer 1980.
	I	Ihara, Y., "Discrete subgroups of PL(2,k )" , Proc. of Syrup. in Pure Math. Series IX, A.M.S. (1966) 272-278. lJ
	LPS	Lubotzky, A., Phillips, R. and Sarnak, P., "Ramanujan graphs", Preprint 1986.
	M	Margulis, G.A., "Explicit constructions of concentrators", Problemy Inf. Trans. 9 (1973) 325-332.
	PIN	Pinsker, "On the complexity of a concentrato#', Proc. 7th Int. Teletraffic Conf. (1973), 318.
	P1	Pippenger, N., "The complexity theory of switching networks", Ph.D. Thesis, M.I.T. 1973.
	P2	Pippenger, N., "S~pereoncentrators", Siam. Jnl. Comp. 6 (1977) 298-304.
	P3	Pippenger, N., "Sorting and selecting in rounds", Preprint 1986.
	P4	Pippenger, N., "Networks of noisy gates", Conf. 26 th I. E. E.E. Syrup. Found. Comp. Sci. 1985, 30-38.
	R	Ramanujan, S., "On certain arithmetical functions",Trans. Camb. Phil. Soc. 22, No.% (1916), 159-184.
	T	Tanner, R.M., "Explicit concentrators from generalized N-gons", Siam. J. Alg. Disc. Methods 5 (1984) 287-293.

CITED BY 24

	E. Upfal, An O(logN) deterministic packet routing scheme, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.241-249, May 14-17, 1989, Seattle, Washington, United States
	Nicholas Pippenger , Geng Lin, Fault-tolerant circuit-switching networks, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.229-235, June 29-July 01, 1992, San Diego, California, United States
	D. Peleg , E. Upfal, Constructing disjoint paths on expander graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.264-273, January 1987, New York, New York, United States
	Oded Goldreich , Avi Wigderson, Tiny families of functions with random properties (preliminary version): a quality-size trade-off for hashing, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.574-584, May 23-25, 1994, Montreal, Quebec, Canada
	Eli Upfal, Tolerating linear number of faults in networks of bounded degree, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.83-89, August 10-12, 1992, Vancouver, British Columbia, Canada
	M. Ajtai , J. Komlos , E. Szemeredi, Deterministic simulation in LOGSPACE, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.132-140, January 1987, New York, New York, United States
	Y. Kohayakawa , V. Rödl , L. Thoma, An optimal algorithm for checking regularity: (extended abstract), Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.277-286, January 06-08, 2002, San Francisco, California
	J. Naor , M. Naor, Small-bias probability spaces: efficient constructions and applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.213-223, May 13-17, 1990, Baltimore, Maryland, United States
	C Dwork , D Peleg , N Pippenger , E Upfal, Fault tolerance in networks of bounded degree, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.370-379, May 28-30, 1986, Berkeley, California, United States
	Rajesh K. Pankaj, Wavelength requirements for multicasting in all-optical networks, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.414-424, June 1999
	Russell Impagliazzo , Noam Nisan , Avi Wigderson, Pseudorandomness for network algorithms, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.356-364, May 23-25, 1994, Montreal, Quebec, Canada
	Joel Friedman, A proof of alon's second eigenvalue conjecture, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	John D. Lafferty , Daniel N. Rockmore, Spectral techniques for expander codes, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.160-167, May 04-06, 1997, El Paso, Texas, United States
	Eli Upfal, An O(log N) deterministic packet-routing scheme, Journal of the ACM (JACM), v.39 n.1, p.55-70, Jan. 1992
	Matthew J. Katz , Micha Sharir, An expander-based approach to geometric optimization, Proceedings of the ninth annual symposium on Computational geometry, p.198-207, May 18-21, 1993, San Diego, California, United States
	Noga Alon , Manuel Blum , Amos Fiat , Sampath Kannan , Moni Naor , Rafail Ostrovsky, Matching nuts and bolts, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.690-696, January 23-25, 1994, Arlington, Virginia, United States
	J. Friedman , J. Kahn , E. Szemerédi, On the second eigenvalue of random regular graphs, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.587-598, May 14-17, 1989, Seattle, Washington, United States
	Dahlia Malkhi , Julien Stern, Scalable secure storage when half the system is faulty, Information and Computation, v.174 n.2, p.203-213, May 1 2002
	Nathan Linial , Eran London, On the expansion rate of Margulis expanders, Journal of Combinatorial Theory Series B, v.96 n.3, p.436-442, May 2006
	Michael Luby , Avi Wigderson, Pairwise independence and derandomization, Foundations and Trends® in Theoretical Computer Science, v.1 n.4, p.237-301, August 2006
	Noga Alon , Haim Kaplan , Michael Krivelevich , Dahlia Malkhi , Julien Stern, Addendum: Addendum to “Scalable secure storage when half the system is faulty” [Inform. Comput. 174 (2)(2002) 203--213], Information and Computation, v.205 n.7, p.1114-1116, July, 2007
	Alon Amit , Nathan Linial, Random Lifts of Graphs: Edge Expansion, Combinatorics, Probability and Computing, v.15 n.3, p.317-332, May 2006
	Noga Alon, On the Edge-Expansion of Graphs, Combinatorics, Probability and Computing, v.6 n.2, p.145-152, June 1997
	R. Beigel , S. R. Kosaraju , G. F. Sullican, Locating faults in a constant number of parallel testing rounds, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.189-198, June 18-21, 1989, Santa Fe, New Mexico, United States