Pseudorandomness for network algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Pseudorandomness for network algorithms

Full text

Pdf (889 KB)

Source

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

Montreal, Quebec, Canada

Pages: 356 - 364

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Russell Impagliazzo	Dept. of Computer Science, UCSD
Noam Nisan	Institute of Computer Science, Hebrew University of Jerusalem, Israel
Avi Wigderson	Institute of Computer Science, Hebrew University of Jerusalem, Israel

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): 10, Citation Count: 14

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

	AC88	N. Alon , F. R. K. Chung, Explicit construction of linear sized tolerant networks, Discrete Mathematics, v.72 n.1-3, p.15-19, December 1988 [doi>10.1016/0012-365X(88)90189-6]
	AS90	N. Alon , P. Seymour , R. Thomas, A separator theorem for graphs with an excluded minor and its applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.293-299, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100254]
	AW85	M. Ajtai and A. Wigderson. Deterministic simulation of probabilistic constant depth circuits. In 26th FOGS, pages 11-19, 1985.
	BFNW	László Babai , Lance Fortnow , Noam Nisan , Avi Wigderson, BPP has subexponential time simulations unless EXPTIME has publishable proofs, Computational Complexity, v.3 n.4, p.307-318, Oct. 1993 [doi>10.1007/BF01275486]
	BM82	M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudo-random bits. In 23rd FOCS, pages 112-117, 1982.
	BNS89	L. Babai , N. Nisan, Multiparty protocols and logspace-hard pseudorandom sequences, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.1-11, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73008]
	GKL88	O. Goldreich, H. Krawcyzk, M. Luby. On the Existence of Pseudorandom Generators. In 29th FOCS, pp. 12-24, 1988.
	Has90	J. Håstad, Pseudo-random generators under uniform assumptions, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.395-404, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100270]
	ILL89	R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73009]
	LPS86	A Lubotzky , R Phillips , P Sarnak, Explicit expanders and the Ramanujan conjectures, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.240-246, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12154]
	LT79	R.J. Lipton, R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math. 36, pp. 177-189, 1979.
	LVW93	M. Luby, B. Velickovic, A. Wigderson. Deterministic Approximate Counting of Depth-2 Circuits. In Proc. of the 2nd ISTCS (Israeh Symposium on Theoretzcal Computer Science), pp. 18-24, 1993.
	Nis91	N. Nisan. Pseudorandom bits for constant depth circuits, in Combinatorica 11 (1), pp. 63-70, 1991.
	Nis92	N. Nisan. Pseudo-random sequences for space bounded computation. In Combinatorica 12 (4), pp 449-461, 1992.
	NW88	N. Nisan and A. Wigderson. Hardness vs. randomness. In FOCS, 1988.
	NZ93	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]
	Re92	Bruce A. Reed, Finding approximate separators and computing tree width quickly, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.221-228, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129734]
	We87	Ingo Wegener, The complexity of Boolean functions, John Wiley & Sons, Inc., New York, NY, 1987
	Y79	Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]
	Yao82	A. C. Yao. Theory and applications of trapdoor functions. In FOCS, pages 80-91, 1982.

CITED BY 14

	Peter Auer , Philip M. Long , Aravind Srinivasan, Approximating hyper-rectangles: learning and pseudo-random sets, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.314-323, May 04-06, 1997, El Paso, Texas, United States
	Ran Raz , Omer Reingold, On recycling the randomness of states in space bounded computation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.159-168, May 01-04, 1999, Atlanta, Georgia, United States
	Krzysztof Diks , Pierre Fraigniaud , Evangelos Kranakis , Andrzej Pelc, Tree exploration with little memory, Journal of Algorithms, v.51 n.1, p.38-63, 1 April 2004
	Alexander Healy , Salil Vadhan , Emanuele Viola, Using nondeterminism to amplify hardness, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Eyal Rozenman , Aner Shalev , Avi Wigderson, A new family of Cayley expanders (?), Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Michal Koucký, Universal traversal sequences with backtracking, Journal of Computer and System Sciences, v.65 n.4, p.717-726, December 2002
	Pierre Fraigniaud , David Ilcinkas , Guy Peer , Andrzej Pelc , David Peleg, Graph exploration by a finite automaton, Theoretical Computer Science, v.345 n.2-3, p.331-344, 22 November 2005
	Omer Reingold, Undirected ST-connectivity in log-space, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Bella Dubrov , Yuval Ishai, On the randomness complexity of efficient sampling, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	ERAN OFEK, On the Expansion of the Giant Component in Percolated (n, d,λ) Graphs, Combinatorics, Probability and Computing, v.16 n.3, p.445-457, May 2007
	Dieter van Melkebeek, A survey of lower bounds for satisfiability and related problems, Foundations and Trends in Theoretical Computer Science, v.2 n.3, p.197-303, January 2006
	Leszek Gasieniec , Andrzej Pelc , Tomasz Radzik , Xiaohui Zhang, Tree exploration with logarithmic memory, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.585-594, January 07-09, 2007, New Orleans, Louisiana
	Omer Reingold, Undirected connectivity in log-space, Journal of the ACM (JACM), v.55 n.4, p.1-24, September 2008
	Pierre Fraigniaud , David Ilcinkas , Andrzej Pelc, Impact of memory size on graph exploration capability, Discrete Applied Mathematics, v.156 n.12, p.2310-2319, June, 2008