On extracting randomness from weak random sources (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On extracting randomness from weak random sources (extended abstract)

Full text

Pdf (830 KB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 276 - 285

Year of Publication: 1996

ISBN:0-89791-785-5

Author

Amnon Ta-Shma

Institute of Computer Science, Hebrew University of Jerusalem

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 21, Citation Count: 21

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

	AKSS89	M. Ajtai, J. Komlos, W. Steiger, and E. Szemeredi. Almost sorting in one round. In Advances in Computer Research, volume 5, pages 117-125, 1989.
	CG88	Benny Chor , Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing, v.17 n.2, p.230-261, April 1988 [doi>10.1137/0217015]
	GW94	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 [doi>10.1145/195058.195410]
	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]
	Pip87	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]
	SSZ95	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 [doi>10.1145/225058.225188]
	SZ94	A. Srinivasan and D. Zuckerman. Computing with very weak random sources. In Proceedings of the 35th Annual IEEE Symposium on the Foundations of Computer Science, 1994.
	WZ93	Avi Wigderson , David Zuckerman, Expanders that beat the eigenvalue bound: explicit construction and applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.245-251, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167163]
	Zuc	D. Zuckerman. Randomness-optimal sampling, extractors, and constructive leader election. Private Communication.
	Zuc90	D. Zuckerman. General weak random sources. In Proceedings of the 31st Annual 7EEE Symposium on the Foundations o/ Computer Sczence, pages 534-543, 1990.
	Zuc91	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]
	Zuc93	D. Zuckerman. NP-complete problems have a version that's hard to approximate. In Proceedings o/ the 8th Structures ~n Complexity Theory, IEEE, pages 305-312, 1993.

CITED BY 21

	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
	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
	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
	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
	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
	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
	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
	Alexander E. Andreev , Andrea E. F. Clementi , José D. P. Rolim, A new general derandomization method, Journal of the ACM (JACM), v.45 n.1, p.179-213, Jan. 1998
	Extractors and pseudorandom generators, Journal of the ACM (JACM), v.48 n.4, p.860-879, July 2001
	Chi-Jen Lu , Omer Reingold , Salil Vadhan , Avi Wigderson, Extractors: optimal up to constant factors, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	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
	Ran Raz, Extractors with weak random seeds, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Ronen Shaltiel , Christopher Umans, Simple extractors for all min-entropies and a new pseudorandom generator, Journal of the ACM (JACM), v.52 n.2, p.172-216, March 2005
	D. Dellamonica, Jr. , Y. Kohayakawa, An algorithmic Friedman--Pippenger theorem on tree embeddings and applications to routing, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1038-1044, January 22-26, 2006, Miami, Florida
	Luis Antunes , Lance Fortnow , Dieter van Melkebeek , N. V. Vinodchandran, Computational depth: concept and applications, Theoretical Computer Science, v.354 n.3, p.391-404, 4 April 2006
	Amnon Ta-Shma, Almost optimal dispersers, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.196-202, May 24-26, 1998, Dallas, Texas, United States
	Amnon Ta-Shma , David Zuckerman , Shmuel Safra, Extractors from Reed-Muller codes, Journal of Computer and System Sciences, v.72 n.5, p.786-812, August 2006
	Jesse Kamp , Anup Rao , Salil Vadhan , David Zuckerman, Deterministic extractors for small-space sources, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Zeev Dvir , Amir Shpilka, An Improved Analysis of Linear Mergers, Computational Complexity, v.16 n.1, p.34-59, May 2007
	Hung Q. Ngo , Yang Wang , Dazhen Pan, Rearrangeable and nonblocking [w, f] -distributors, IEEE/ACM Transactions on Networking (TON), v.17 n.3, p.990-1001, June 2009
	Zeev Dvir , Ran Raz, Analyzing linear mergers, Random Structures & Algorithms, v.32 n.3, p.334-345, May 2008

INDEX TERMS

Primary Classification:
G. Mathematics of Computing

General Terms:
Theory, Verification

Collaborative Colleagues:

Amnon Ta-Shma: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player