×

zbMATH — the first resource for mathematics

Pseudo-random generators for all hardnesses. (English) Zbl 1072.68129
Summary: Given a function \(f: \{0,1\}^{\log n}\to\{0,1\}\) with circuit complexity \(s\), we construct a pseudo-random generator that stretches a random seed of length \(O(\log n)\) into a string of \(m=s^{\Omega(1)}\) pseudo-random bits that fool circuits of size \(m\). The construction works for any hardness \(s\), giving an optimal hardness vs. randomness tradeoff with a direct and self-contained proof. A key element in our construction is an augmentation of the standard low-degree extension encoding that exploits the field structure of the underlying space in a new way.

MSC:
68W20 Randomized algorithms
65C10 Random number generation in numerical analysis
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andreev, A.; Clementi, A.; Rolim, J., A new general derandomization method, J. ACM, 45, 1, (1998) · Zbl 0903.68089
[2] A.E. Andreev, A.E.F. Clementi, J.D.P. Rolim, L. Trevisan, Weak random sources, hitting sets, and BPP simulations, in: 38th Annual Symposium on Foundations of Computer Science, Miami Beach, FL, 20-22 October, IEEE, New York, 1997, pp. 264-272. · Zbl 0943.68064
[3] Babai, L.; Fortnow, L.; Nisan, N.; Wigderson, A., BPP has subexponential time simulations unless EXPTIME has publishable proofs, Comput. complexity, 3, 4, 307-318, (1993) · Zbl 0802.68054
[4] M. Bellare, J. Rompel, Randomness-efficient oblivious sampling, in: 35th Annual Symposium on Foundations of Computer Science, 1994.
[5] Blum, M.; Micali, S., How to generate cryptographically strong sequences of pseudo-random bits, SIAM J. comput., 13, 4, 850-864, (1984) · Zbl 0547.68046
[6] O. Goldreich, S. Vadhan, A. Wigderson, Simplified derandomization of BPP using a hitting set generator, Technical Report TR00-004, Electronic Colloquium on Computational Complexity, January 2000. · Zbl 1343.68303
[7] V. Guruswami, M. Sudan, List decoding algorithms for certain concatenated codes, in: Proceedings of the 32nd ACM Symposium on Theory of Computing, 2000. · Zbl 1296.94170
[8] V. Guruswami, M. Sudan, Extensions to the Johnson bound, Manuscript, February 2001.
[9] R. Impagliazzo, Hard-core distributions for somewhat hard problems. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, WI, 23-25 October, IEEE, New York, 1995, pp. 538-545. · Zbl 0938.68921
[10] R. Impagliazzo, V. Kabanets, A. Wigderson, In search of an easy witness: Exponential time vs. probabilistic polynomial time, in: Sixteenth Annual IEEE Conference on Computational Complexity, 2001, pp. 1-12; J. Comput. System Sci., to appear. · Zbl 1059.68047
[11] R. Impagliazzo, R. Shaltiel, A. Wigderson, Near-optimal conversion of hardness into pseudo-randomness, in: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999.
[12] R. Impagliazzo, R. Shaltiel, A. Wigderson, Extractors and pseudo-random generators with optimal seed-length, in: Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing, 21-23 May 2000. · Zbl 1296.65007
[13] R. Impagliazzo, A. Wigderson, P=BPP if E requires exponential circuits: Derandomizing the XOR lemma, in: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, El Paso, Texas, 4-6 May 1997, pp. 220-229. · Zbl 0962.68058
[14] Kabanets, V., Easiness assumptions and hardness teststrading time for zero error, J. comput. system sci., 63, 2, 236-252, (2001) · Zbl 0988.68221
[15] A.R. Klivans, D. van Melkebeek, Graph nonisomorphism has subexponential size proofs unless the polynomial-times hierarchy collapses, in: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, SIAM J. Comput., to appear. · Zbl 1345.68174
[16] Lang, S., Algebra, (1993), Addison-Wesley Reading, MA
[17] Lu, C.J., Derandomizing arthur – merlin games under uniform assumptions, Comput. complexity, 10, 3, 247-259, (2001) · Zbl 0993.68038
[18] P.B. Miltersen, N.V. Vinodchandran, Derandomizing Arthur-Merlin games using hitting sets, in: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999. · Zbl 1085.68058
[19] Nisan, N.; Wigderson, A., Hardness vs randomness, J. comput. system sci., 49, 2, 149-167, (1994) · Zbl 0821.68057
[20] R. Shaltiel, C. Umans, Simple extractors for all min-entropies and a new pseudo-random generator, in: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, 2001, pp. 648-657.
[21] Sudan, M., Decoding of Reed Solomon codes beyond the error-correction bound, J. complexity, 13, (1997) · Zbl 0872.68026
[22] Sudan, M.; Trevisan, L.; Vadhan, S., Pseudorandom generators without the XOR lemma, J. comput. system sci., 62, 2, 236-266, (2001) · Zbl 1005.65006
[23] A. Ta-Shma, D. Zuckerman, S. Safra, Extractors from Reed-Muller codes, in: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, 2001. · Zbl 1094.68036
[24] Trevisan, L., Extractors and pseudorandom generators, J. ACM, 48, 4, 860-879, (2001) · Zbl 1127.68403
[25] R. Urbanke, Modern coding theory—SS2001, Technical Report DSC-LTHC, EPFL, 2001, Available from http://lthcwww.epfl.ch/content.php?title=coding2001.
[26] A.C. Yao, Theory and applications of trapdoor functions (extended abstract), in: 23rd Annual Symposium on Foundations of Computer Science, Chicago, IL, 3-5 November, IEEE, New York, 1982, pp. 80-91.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.