Expanders that beat the eigenvalue bound

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Expanders that beat the eigenvalue bound: explicit construction and applications

Full text

Pdf (624 KB)

Source

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

San Diego, California, United States

Pages: 245 - 251

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Avi Wigderson
David Zuckerman

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 17, 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/167088.167163 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.

	AKS1	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]
	AKS2	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 [doi>10.1145/28395.28410]
	AKSS	M. Ajtai, J. Komlos, W. Steiger, and E. Szemeredi, "Almost Sorting in One Round," Advances in Computing Research, Vol. 5, 1989, pp. 117-125.
	Alol	N Alon, Expanders, sorting in rounds and superconcentrators of limited depth, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.98-102, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22156]
	Alo2	N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
	AA	Noga Alon , Yossi Azar, Sorting, approximate sorting, and searching in rounds, SIAM Journal on Discrete Mathematics, v.1 n.3, p.269-280, Aug. 1988 [doi>10.1137/0401028]
	AM	N. Alon and V.D. Milman, ")#1, Isoperimettic Inequalities for Graphs and Supereoneentrators," J. Combinatorial Theory Ser. B 38 (1985), pp. 73-88.
	AP	Y. Azar , N. Pippenger, Parallel selection, Discrete Applied Mathematics, v.27 n.1-2, p.49-58, May 1990 [doi>10.1016/0166-218X(90)90128-Y]
	BH	B. Bollobas and A. Thomason, "Parallel Sorting," Discrete Appl. Math. 6 (1983), pp. 1-11.
	DDPW	Danny Dolev , Cynthia Dwork , Nicholas Pippenger , Avi Wigderson, Superconcentrators, generalizers and generalized connectors with limited depth, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.42-51, December 1983 [doi>10.1145/800061.808731]
	FFP	Paul Feldman , Joel Friedman , Nicholas Pippengers, Wide-sense nonblocking networks, SIAM Journal on Discrete Mathematics, v.1 n.2, p.158-173, May 1988 [doi>10.1137/0401018]
	GG	O. Gabber and Z. Galil, "Explicit Construction of Linear Sized Superconcentrators," J. Comp. and Sys. Sc# 22 (1981), pp. 407-420.
	GIL+	O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesan, and D. Zuckerman, "Security Preserving Amplification of Hardness," 31st FOCS, 1990, pp. 318-326.
	Kah	N. Kahale, "On the Second Eigenvalue and Linear Expansion of Regular Graphs," 33rd FOCS, 1992, pp. 296-303.
	LPS	A. Lubotzky, R. Philips, P. Sarnak, "Ramanujan Graphs," Combznatorzca 8 (1988), pp. 261-277.
	Mar	G.A. Margulis, "Explicit Construction of Concentrators," Problems of Inform. Transmission, pp. 325-332.
	Mes	R. Meshulam, "A Geometric Construction of a Superconcentrator of Depth 2," Theoretical Computer Sczence 32 (1984), pp. 215- 219.
	Mor	Moshe Morgenstern, Explicit construction of natural bounded concentrators, Proceedings of the 32nd annual symposium on Foundations of computer science, p.392-397, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185396]
	NZ	Noam Nisan , David Zuckerman, More deterministic simulation in logspace, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.235-244, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167162]
	Pip1	N. Pippenger, "Superconcentrators," SIAM J. Comput. 6 (1977), pp. 298-304.
	Pip2	N. Fippenger, "Superconcentrators of Depth 2," J. Comp. and Sys. Sci. 24 (1982), pp. 82- 90.
	Pip3	Nicholas Pippenger, Sorting and selecting in rounds, SIAM Journal on Computing, v.16 n.6, p.1032-1038, December 1, 1987 [doi>10.1137/0216066]
	PY	N. Pippenger and A.C. Yao, "Rearrangeable Networks with Limited Depth," SIAM J. Algebraic and Discrete Methods 3 (1982), pp. 411-417.
	Tan	R.M. Tanner, "Explicit Construction of Concentrators from Generalized N-gons," SIAM J. Alg. Discr. Meth. 5 (1984), pp. 287- 293.
	Tom	M. Tompa, "Time Space Tradeoffs for Computing Functions, Using Connectivity Properties of Their Circuits," J. Comp. and Sys. Sci, 20 (1980), pp. 118-132.
	Val1	L.G. Valiant, "Parallelism in Comparison Problems," SIAM J. Comput. 4 (1975), pp. 348-355.
	Val2	L.G. Valiant, "Graph Theoretic Properties in Computational Complexity," J. Comp. and Sys. Sci. 13 (1976), pp. 278-285.
	Zuc1	D. Zuckerman, "General Weak Random Sources," 31st FOCS, 1990, pp. 534-543.
	Zuc2	David Zuckerman, Simulating BPP using a general weak random source, Proceedings of the 32nd annual symposium on Foundations of computer science, p.79-89, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185351]

CITED BY 19

	Noam Nisan , David Zuckerman, More deterministic simulation in logspace, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.235-244, May 16-18, 1993, San Diego, California, United States
	Alok Aggarwal , Amotz Bar-Noy , Don Coppersmith , Rajiv Ramaswami , Baruch Schieber , Madhu Sudan, Efficient routing in optical networks, Journal of the ACM (JACM), v.43 n.6, p.973-1001, Nov. 1996
	Michael Saks , Aravind Srinivasan , Shiyu Zhou, Explicit OR-dispersers with polylogarithmic degree, Journal of the ACM (JACM), v.45 n.1, p.123-154, Jan. 1998
	Alexander Gamburd , Igor Pak, Expansion of product replacement graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.691-696, January 06-08, 2002, San Francisco, California
	David Zuckerman, Randomness-optimal sampling, extractors, and constructive leader election, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.286-295, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Russell Impagliazzo , Ronen Shaltiel , Avi Wigderson, Extractors and pseudo-random generators with optimal seed length, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.1-10, May 21-23, 2000, Portland, Oregon, United States
	Michael Saks , Aravind Srinivasan , Shiyu Zhou, Explicit dispersers with polylog degree, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.479-488, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Alok Aggarwal , Amotz Bar-Noy , Don Coppersmith , Rajiv Ramaswami , Baruch Schieber , Madhu Sudan, Efficient routing and scheduling algorithms for optical networks, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.412-423, January 23-25, 1994, Arlington, Virginia, United States
	Luca Trevisan, Construction of extractors using pseudo-random generators (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.141-148, May 01-04, 1999, Atlanta, Georgia, United States
	Amnon Ta-Shma, On extracting randomness from weak random sources (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.276-285, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Eric A. Brewer , Frederic T. Chong , Tom Leighton, Scalable expanders: exploiting hierarchical random wiring, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.144-152, May 23-25, 1994, Montreal, Quebec, Canada
	Extractors and pseudorandom generators, Journal of the ACM (JACM), v.48 n.4, p.860-879, July 2001
	Noam Nisan , Avi Wigderson, On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.723-732, May 29-June 01, 1995, Las Vegas, Nevada, United States
	William Gasarch , Evan Golub , Clyde Kruskal, Constant time parallel sorting: an empirical view, Journal of Computer and System Sciences, v.67 n.1, p.63-91, August 2003
	Avi Wigderson, The amazing power of pairwise independence (abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.645-647, May 23-25, 1994, Montreal, Quebec, Canada
	Amnon Ta-Shma, Storing information with extractors, Information Processing Letters, v.83 n.5, p.267-274, 15 September 2002
	Yijie Han, Optimal parallel selection, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Yijie Han, Optimal parallel selection, ACM Transactions on Algorithms (TALG), v.3 n.4, p.38-es, November 2007
	Harold N. Gabow, Using expander graphs to find vertex connectivity, Journal of the ACM (JACM), v.53 n.5, p.800-844, September 2006