Pseudorandom generators for space-bounded computations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Pseudorandom generators for space-bounded computations

Full text

Pdf (755 KB)

Source

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

Baltimore, Maryland, United States

Pages: 204 - 212

Year of Publication: 1990

ISBN:0-89791-361-2

Author

N. Nisan

Laboratory for Computer science, MIT, 545 Tech. sq., Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 83, Citation Count: 25

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

	AKL+79	R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovasz, and C. Rackoff. Random walks, universal sequences and the complexity of maze problems. In 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1979.
	AKS87	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]
	AW85	M. Ajtai and A. Wigderson. Deterministic simulation of probabilistic constant depth circuits". In 26 th Annual Symposium on Foundations of Computer Science, Portland, Oregon, pages 11-19, October 1985.
	BM84	Manuel Blum , Silvio Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM Journal on Computing, v.13 n.4, p.850-864, Nov. 1984 [doi>10.1137/0213053]
	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]
	CG86	B. Chor and O. Goldreich. On the power of two points biased sampling. 1986.
	CW79	L. Carter and M. Wegman. Universal hash functions. J. Comp. and Syst. Sci., 18(2):143-154, 1979.
	CW89	A. Cohen and A. Wigderson. Dispersers, deterministic amplification, and weak random sources. In 30 th Annual Symposium on Foundations of Computer Science, Reseach Triangle Park, NC, pages 14-19, October 1989.
	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]
	Ist88	Sorin Istrail, Polynomial universal traversing sequences for cycles are constructible, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.491-503, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62260]
	IZ89	R. Impagliazzo and D. Zuckerman. How to recycle random bits. In 30 th Annual Symposium on Foundations of Computer Science, Reseach Triangle Park, NC, pages 248-253, October 1989.
	KPS85	R. Karp, N. Pippenger, and M. Sipser. A time-randomness tradeoff. In AMS Conference on Probabilistic Computational Complexity, 1985.
	KPS87	H. Karloff, R. Paturi, and J. Simon. Universal sequences of length n0logn for cliques. Manuscript, 1987.
	MNT89	Y. Mansour, N. Nisan, and P. Tiwari. The computational complexity of universal hashing, manuscrip, 1989.
	NW88	N. Nisan and A. Wigderson. Hardness vs. randomness. In 29 th Annual Symposium on Foundations of Computer Science, White Plains, New York, pages 2-12, October 1988.
	Rab80	M.O. Rabin. Probabilistic algorithm for testing primality. J. of number theory, 12:128-138, 1980.
	San	M. Santha. On using deterministic functions to reduce randomness in probabilistic algorithms, manuscript.
	Sip86	M Sipser, Expanders, randomness, or time versus space, Proc. of the conference on Structure in complexity theory, p.325-329, June 1986, Berkeley, California, United States
	Vaz87	U. Vazirani, Efficiency considerations in using semi-random sources, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.160-168, January 1987, New York, New York, United States [doi>10.1145/28395.28413]
	Yao82	A. C. Yao. Theory and applications of trapdoor functions. In 23th Annual Symposium on Foundations of Computer Science, pages 80-91, October 1982.

CITED BY 25

	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
	David R. Karger , Noam Nisan , Michal Parnas, Fast connected components algorithms for the EREW PRAM, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.373-381, June 29-July 01, 1992, San Diego, California, United States
	Guy Even , Oded Goldreich , Michael Luby , Noam Nisan , Boban Veličkovic, Approximations of general independent distributions, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.10-16, May 04-06, 1992, Victoria, British Columbia, Canada
	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
	Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Amortizing randomness in private multiparty computations, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.81-90, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Mihalis Yannakakis , David Lee, Testing finite state machines, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.476-485, May 05-08, 1991, New Orleans, Louisiana, United States
	D. Sivakumar, Algorithmic derandomization via complexity theory, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Nati Linial , Michael Luby , Michael Saks , David Zuckerman, Efficient construction of a small hitting set for combinatorial rectangles in high dimension, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.258-267, May 16-18, 1993, San Diego, California, United States
	Eyal Kushilevitz , Yishay Mansour, Randomness in private computations, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.181-190, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Noam Nisan, RL⊆SC, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.619-623, May 04-06, 1992, Victoria, British Columbia, Canada
	Greg Barnes , Walter L. Ruzzo, Deterministic algorithms for undirected s-t connectivity using polynomial time and sublinear space., Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.43-53, May 05-08, 1991, New Orleans, Louisiana, United States
	H. Buhrman , P. B. Miltersen , J. Radhakrishnan , S. Venkatesh, Are bitvectors optimal?, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.449-458, May 21-23, 2000, Portland, Oregon, United States
	Ran Canetti , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén, Randomness vs. fault-tolerance, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.35-44, August 21-24, 1997, Santa Barbara, California, United States
	Lakshminath Bhuvanagiri , Sumit Ganguly , Deepanjan Kesh , Chandan Saha, Simpler algorithm for estimating frequency moments of data streams, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.708-713, January 22-26, 2006, Miami, Florida
	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
	Uriel Feige , Yuri Rabinovich, Deterministic approximation of the cover time, Random Structures & Algorithms, v.23 n.1, p.1-22, August 2003
	Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, One-Pass Wavelet Decompositions of Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.541-554, March 2003
	S. Muthukrishnan , Martin Strauss, Rangesum histograms, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Gereon Frahling , Piotr Indyk , Christian Sohler, Sampling in dynamic data streams and applications, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Vladimir Trifonov, An O(log n log log n) space algorithm for undirected st-connectivity, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Anna C. Gilbert , Sudipto Guha , Piotr Indyk , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, Fast, small-space algorithms for approximate histogram maintenance, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Noam Nisan , Avi Widgerson, Rounds in communication complexity revisited, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.419-429, May 05-08, 1991, New Orleans, Louisiana, United States
	Piotr Indyk, Stable distributions, pseudorandom generators, embeddings, and data stream computation, Journal of the ACM (JACM), v.53 n.3, p.307-323, May 2006
	Sumit Ganguly, Counting distinct items over update streams, Theoretical Computer Science, v.378 n.3, p.211-222, June, 2007
	Omer Reingold, Undirected connectivity in log-space, Journal of the ACM (JACM), v.55 n.4, p.1-24, September 2008