Pseudorandom generators without the XOR Lemma (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Pseudorandom generators without the XOR Lemma (extended abstract)

Full text

Pdf (946 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: 537 - 546

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Madhu Sudan	Laboratory for Computer Science, 545 Technology Square, MIT, Cambridge, MA
Luca Trevisan	Department of Computer Science, Columbia University, 500W 120th St., New York, NY
Salil Vadhan	Laboratory for Computer Science, 542 Technology Square, MIT, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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.301397 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.

	ACR97	Alexander E. Andreev , Andrea E. F. Clementi , José D. P. Rolim, Worst-Case Hardness Suffices for Derandomization: A New Method for Hardness-Randomness Trade-Offs, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.177-187, July 07-11, 1997
	AK97	Vikraman Arvind , Johannes Köbler, On Resource-Bounded Measure and Pseudorandomness, Proceedings of the 17th Conference on Foundations of Software Technology and Theoretical Computer Science, p.235-249, December 18-20, 1997
	ALRS92	Sigal At, Richard J. Lipton, Ronitt Rubinfeld, and Madhu Sudan. Reconstructing algebraic functions from mixed data. In 33rd Annual Symposium on Foundations of Computer Science, pages 503-512, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
	AS97	Sanjeev Arora , Madhu Sudan, Improved low-degree testing and its applications, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.485-495, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258642]
	BBR85	Charles H Bennett , Gilles Brassard , Jean-Marc Robert, How to reduce your enemy's information, Lecture notes in computer sciences; 218 on Advances in cryptology---CRYPTO 85, p.468-476, June 1986, Santa Barbara, California, United States
	BF90	Donald Beaver , J. Feigenbaum, Hiding instances in multioracle queries, Proceedings of the seventh annual symposium on Theoretical aspects of computer science, p.37-48, February 1990, Rouen, France
	BFNW93	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]
	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]
	CG89	B. Chor , O. Goldreich, On the power of two-point based sampling, Journal of Complexity, v.5 n.1, p.96-106, March 1989 [doi>10.1016/0885-064X(89)90015-0]
	CGH+85	Benny Chor, Oded Goldreich, Johan Hastad, Joel Friedman, Steven Rudieh, and Roman Smolensky. The bit extraction problem or t-resilient functions (preliminary version). In 26th Annual Symposium on Foundations of Computer Science, pages 396-407, Porfiand, Oregon, 21-23 October 1985. IEEE.
	CPS99	Jin-Yi Cai, A. Pavan, and D. Sivakumar. On the hardness of the permanent. In 16th International Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Trier, Germany, March 4-6 1999. Springer-Verlag. To appear.
	CT91	Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
	CW89	Aviad Cohen and Avi Wigderson. Dispersers, determinislic amplification, and weak random sources (extended abstrac0. In 30th Annual Symposium on Foundations of Computer Science, pages 14-19, Research Triangle Park, North Carolina, 30 October-I November t989. IEEE.
	FF93	Joan Feigenbaum , Lance Fortnow, Random-self-reducibility of complete sets, SIAM Journal on Computing, v.22 n.5, p.994-1005, Oct. 1993 [doi>10.1137/0222061]
	FL96	Uriel Feige , Carsten Lund, On the hardness of computing the permanent of random matrices, Computational Complexity, v.6 n.2, p.101-132, 1996/1997 [doi>10.1007/BF01262928]
	Fri92	loet Friedman. On the bit extraction problem, In 33rdAnnual Symposium on Foundations of Computer Science, pages 314- 319, Pittsburgh, Pennsylvania, 24--27 October 1992. IEEE.
	GL89	O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
	GLR+91	Peter Gemmell , Richard Lipton , Ronitt Rubinfeld , Madhu Sudan , Avi Wigderson, Self-testing/correcting for polynomials and for approximate functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.33-42, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103429]
	GM84	Shaft Goldwasser and Silvio Micali. Probabilistic encryplion. Journal of Computer and System Sciences, 28(2):270- 299, April t 984.
	GNW95	Oded Goldreich, Noam Nisan, and Avi Wigderson. On Yao's XOR lemma. Technical Report TR95--050, Electronic Colloquium on Computational Complexity, March 1995. http: / / www. eccc. uni- trier, de / eccc.
	Gol95	Oded Goldreich. Foundations of Cryptography (Fragments of a Book). Weizmann Institute of Science, 1995. Available, along with revised version 1/98, from http:// www. wisdom, weizmann, ac. 51 / ~oded.
	Gol97a	Oded Goldreich. A computational perspective on sampling (survey). Available from http: / / www. wis dora. wel zmann, ac. i 1 / ~odor/, May 1997.
	Gol97b	Oded Goldreich. Three XOR lemmas- an exposition. Available from http://www.wisdom.weizmann.ac, il/ -oded/, November 1997.
	Gol98	Oded Goldreich , R. L. Graham , B. Korte, Modern Cryptography, Probabilistic Proofs, and Pseudorandomness, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
	GRS98	O. Goldreich , R. Rubinfeld , M. Sudan, Learning polynomials with queries: The highly noisy case, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.294, October 23-25, 1995
	GS92	Peter Gemmell , Madhu Sudan, Highly resilient correctors for polynomials, Information Processing Letters, v.43 n.4, p.169-174, Sept. 28, 1992 [doi>10.1016/0020-0190(92)90195-2]
	GS98	Venkatesan Guruswami , Madhu Sudan, Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.28, November 08-11, 1998
	HILL98	J. H,Sstad, R. Impagliazzo, L. Levin, and M. Luby. A pseudorandom generator from any one-way function. To appear in SIAM J. on Computing, 1998.
	Imp95	R. Impagliazzo, Hard-core distributions for somewhat hard problems, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.538, October 23-25, 1995
	IW97	Russell Impagliazzo , Avi Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.220-229, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258590]
	IW98	R. Impagliazzo , A. Wigderson, Randomness vs. Time: De-Randomization under a Uniform Assumption, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.734, November 08-11, 1998
	KS98	S. Ravi Kumar and D. Sivakumar. Personal communication, October 1998.
	KvM98	Adam Klivans , Dieter Van Melkebeek, Graph Nonisomorphism Has Subexponential Size Proofs Unless The Polynomial-Time Hierarchy Collapses, University of Chicago, Chicago, IL, 1998
	Lip89	Richard Lipton. New directions in testing. In Proceedings of DIMACS Workshop on Distributed Computing and Cryptography, 1989.
	NW94	Noam Nisan , Avi Wigderson, Hardness vs. randomness, Journal of Computer and System Sciences, v.49 n.2, p.149-167, Oct. 1994 [doi>10.1016/S0022-0000(05)80043-1]
	NZ96	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]
	STV98	Madhu Sudan, Luca Trevisan, and Salil Vadhan. Pseudorandom generators without the XOR temma. Technical Report TR98-074, Electronic Colloquium on Computational Complexity, December 1998. http://www.eccc.uni-trier, de/eccc.
	Sud97	Madhu Sudan, Decoding of Reed Solomon codes beyond the error-correction bound, Journal of Complexity, v.13 n.1, p.180-193, March 1997 [doi>10.1006/jcom.1997.0439]
	Tre98	Luca Trevisan. Constructions of near-optimal extractors using pseudo-random generators. Technical Report TR98-055, Electronic Colloquium on Computational Complexity, 1998. Extended abstract in these proceedings.
	Vaz85	U V Vazirani, Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.366-378, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22186]
	Wig98	Avi Wigderson. Personal communication, October 1998.
	Yao82	Andrew C. Yao. Theory and applications of trapdoor functions (extended abstracl). In 23rd Annual Symposium on Foundations of Computer Science, pages 80--.91, Chicago, Illinois, 3-5 November 1982. IEEE.
	Zuc96	David Zuckerman. Simulating BPP using a general weak random source. Algorithmica, 16(415):367-391, October/November 1996.

CITED BY 18

	Jonathan Katz , Luca Trevisan, On the efficiency of local decoding procedures for error-correcting codes, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.80-86, May 21-23, 2000, Portland, Oregon, United States
	Christopher Umans, Pseudo-random generators for all hardnesses, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Amnon Ta-Shma , David Zucherman, Extractor codes, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.193-199, July 2001, Hersonissos, Greece
	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
	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
	Extractors and pseudorandom generators, Journal of the ACM (JACM), v.48 n.4, p.860-879, July 2001
	Venkatesan Guruswami , Madhu Sudan, List decoding algorithms for certain concatenated codes, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.181-190, May 21-23, 2000, Portland, Oregon, 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
	Iordanis Kerenidis , Ronald de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Russell Impagliazzo , Valentine Kabanets , Avi Wigderson, In search of an easy witness: exponential time vs. probabilistic polynomial time, Journal of Computer and System Sciences, v.65 n.4, p.672-694, December 2002
	Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Batch codes and their applications, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Iordanis Kerenidis , Ronald de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Journal of Computer and System Sciences, v.69 n.3, p.395-420, November 2004
	Dan Gutfreund , Ronen Shaltiel , Amnon Ta-Shma, Uniform hardness versus randomness tradeoffs for Arthur-Merlin games, Computational Complexity, v.12 n.3-4, p.85-130, September 2004
	Amit Deshpande , Rahul Jain , T. Kavitha , Satyanarayana V. Lokam , Jaikumar Radhakrishnan, Lower bounds for adaptive locally decodable codes, Random Structures & Algorithms, v.27 n.3, p.358-378, October 2005
	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
	Irit Dinur , Elena Grigorescu , Swastik Kopparty , Madhu Sudan, Decodability of group homomorphisms beyond the johnson bound, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Shafi Goldwasser , Dan Gutfreund , Alexander Healy , Tali Kaufman , Guy N. Rothblum, Verifying and decoding in constant depth, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA