On recycling the randomness of states in space bounded computation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On recycling the randomness of states in space bounded computation

Full text

Pdf (889 KB)

Source

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

Atlanta, Georgia, United States

Pages: 159 - 168

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Ran Raz	Department of Applied Mathematics and Computer Science, Weizmann Institute, Rehovot, 76100 Israel
Omer Reingold	Dept. of Applied Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, 76100 Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 17, Citation Count: 10

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

	1	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]
	2	Roy Armoni, On the Derandomization of Space-Bounded Computations, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.47-59, October 08-10, 1998
	3	Roy Armoni , Amnon Ta-Shma , Avi Wigderson , Shiyu Zhou, SL ⊆L^4/3, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.230-239, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258593]
	4	L. Carter and M. Wegman, Universal hash functions, J, of Computer and System Sciences, vol. 18, I979, pp. t43-154.
	5	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 [doi>10.1145/195058.195190]
	6	N. Nisan, Pscudorandom generators for space-bounded computation, Combinatorica, vol, 12(4), 1992, pp. 449-461.
	7	N. Nisan, E. Szemeredi and A. Wigdermn, Undirected connectivity in O(log~ 5 r~) space, Proc. 33rd IEEE Syrup. on Foundations of Computer Science, 1992, pp, 24--29.
	8	Noam Nisan , David Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences, v.52 n.1, p.43-52, Feb. 1996 [doi>10.1006/jcss.1996.0004]
	9	J. Radhakrishnan , A. Ta-Shma, Tight bounds for depth-two superconcentrators, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.585, October 19-22, 1997
	10	Ran Raz , Omer Reingold , Salil Vadhan, Extracting all the randomness and reducing the error in Trevisan's extractors, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.149-158, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301292]
	11	M. Saks and S. Zhou, RSPACE(S) _C DSPACE($3/2), Proc, 36thlEEESymp. on Foundations of Computer Science, 1995, pp, 23-25.
	12	W. J. Savitch, Relationship between nondeterminisfic and deterministic tape complexities, J. Comput. System Sci., vol. 4(2), 1970, pp. 177-192.
	13	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 [doi>10.1145/237814.237877]
	14	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 [doi>10.1145/301250.301289]
	15	David Zuckerman, Randomness-optimal oblivious sampling, Random Structures & Algorithms, v.11 n.4, p.345-367, Dec. 1997

CITED BY 10

	Amnon Ta-Shma , Christopher Umans , David Zuckerman, Loss-less condensers, unbalanced expanders, and extractors, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.143-152, July 2001, Hersonissos, Greece
	Piotr Indyk, Explicit constructions of selectors and related combinatorial structures, with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.697-704, January 06-08, 2002, San Francisco, California
	Ran Raz , Omer Reingold , Salil Vadhan, Extracting all the randomness and reducing the error in Trevisan's extractors, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.149-158, May 01-04, 1999, Atlanta, Georgia, United States
	Ran Raz , Omer Reingold , Salil Vadhan, Extracting all the randomness and reducing the error in Trevisan's extractors, Journal of Computer and System Sciences, v.65 n.1, p.97-128, August 2002
	Tzvika Hartman , Ran Raz, On the distribution of the number of roots of polynomials and explicit weak designs, Random Structures & Algorithms, v.23 n.3, p.235-263, October 2003
	Amnon Ta-Shma, Storing information with extractors, Information Processing Letters, v.83 n.5, p.267-274, 15 September 2002
	Michael Capalbo , Omer Reingold , Salil Vadhan , Avi Wigderson, Randomness conductors and constant-degree lossless expanders, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	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
	Luca Trevisan , Salil Vadhan , David Zuckerman, Compression of samplable sources, Computational Complexity, v.14 n.3, p.186-227, January 2005
	Omer Reingold, Undirected connectivity in log-space, Journal of the ACM (JACM), v.55 n.4, p.1-24, September 2008