The unified theory of pseudorandomness: guest column

ABSTRACT

We survey the close connections between a variety of "pseudorandom objects," namely pseudorandom generators, expander graphs, list-decodable error-correcting codes, randomness extractors, averaging samplers, and hardness amplifiers.

REFERENCES

• 1: N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
• 2: 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]
• 3: M. Bellare and J. Rompel. Randomness-efficient oblivious sampling. In Proc. 35th FOCS, pages 276--287, 1994.
• 4: 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]
• 5: 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]
• 6: 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]
• 7: A. E. F. Clementi, J. D. P. Rolim, and L. Trevisan. Recent advances towards proving P=BPP. Bull. of the EATCS, 64:96--103, 1998.
• 8: David Galvin , Prasad Tetali, Slow mixing of Glauber dynamics for the hard-core model on regular bipartite graphs, Random Structures & Algorithms, v.28 n.4, p.427-443, July 2006 [doi>10.1002/rsa.v28:4]
• 9: David Gillman, A Chernoff Bound for Random Walks on Expander Graphs, SIAM Journal on Computing, v.27 n.4, p.1203-1220, Aug. 1998 [doi>10.1137/S0097539794268765]
• 10: O. Goldreich. A sample of samplers - a computational perspective on sampling (survey). Electronic Colloquium on Computational Complexity (ECCC), 4(20), 1997.
• 11: Oded Goldreich , R. L. Graham , B. Korte, Modern Cryptography, Probabilistic Proofs, and Pseudorandomness, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 12: S. Goldwasser and S. Micali. Probabilistic encryption. J. Computer & System Sci., 28(2):270--299, Apr. 1984.
• 13: Venkatesan Guruswami, Algorithmic results in list decoding, Foundations and Trends® in Theoretical Computer Science, v.2 n.2, p.107-195, January 2007 [doi>10.1561/0400000007]
• 14: Venkatesan Guruswami , Christopher Umans , Salil Vadhan, Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.96-108, June 13-March 16, 2007 [doi>10.1109/CCC.2007.38]
• 15: Johan HÅstad , Russell Impagliazzo , Leonid A. Levin , Michael Luby, A Pseudorandom Generator from any One-way Function, SIAM Journal on Computing, v.28 n.4, p.1364-1396, Aug. 1999 [doi>10.1137/S0097539793244708]
• 16: S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bull. of the AMS, 43(4):439--561, 2006.
• 17: V. Kabanets. Derandomization: a brief overview. Bull. of the EATCS, 76:88--103, 2002.
• 18: P. Miltersen. Handbook of Randomized Computing, chapter Derandomizing Complexity Classes. Kluwer, 2001.
• 19: Naom Nisan , Amnon Ta-Shma, Extracting randomness: a survey and new constructions, Journal of Computer and System Sciences, v.58 n.1, p.148-173, Feb. 1999 [doi>10.1006/jcss.1997.1546]
• 20: 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]
• 21: 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]
• 22: Jaikumar Radhakrishnan , Amnon Ta-Shma, Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators, SIAM Journal on Discrete Mathematics, v.13 n.1, p.2-24, Jan. 2000 [doi>10.1137/S0895480197329508]
• 23: Jeanette P. Schmidt , Alan Siegel , Aravind Srinivasan, Chernoff-Hoeffding Bounds for Applications with Limited Independence, SIAM Journal on Discrete Mathematics, v.8 n.2, p.223-250, May 1995 [doi>10.1137/S089548019223872X]
• 24: R. Shaltiel. Recent developments in extractors. In Current Trends in Theoretical Computer Science, vol. 1: Algorithms and Complexity. World Scientific, 2004.
• 25: Madhu Sudan, List decoding: algorithms and applications, ACM SIGACT News, v.31 n.1, p.16-27, March 2000 [doi>10.1145/346048.346049]
• 26: Madhu Sudan , Luca Trevisan , Salil Vadhan, Pseudorandom generators without the XOR lemma, Journal of Computer and System Sciences, v.62 n.2, p.236-266, March 2001 [doi>10.1006/jcss.2000.1730]
• 27: 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 [doi>10.1145/380752.380790]
• 28: A. Ta-Shma and D. Zuckerman. Extractor codes. IEEE Trans. Information Theory, 50(12):3015--3025, 2004.
• 29: Extractors and pseudorandom generators, Journal of the ACM (JACM), v.48 n.4, p.860-879, July 2001 [doi>10.1145/502090.502099]
• 30: L. Trevisan. Some applications of coding theory in computational complexity. Quaderni di Matematica, 13:347--424, 2004.
• 31: Luca Trevisan , Salil Vadhan, Pseudorandomness and Average-Case Complexity via Uniform Reductions, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.129, May 21-24, 2002
• 32: S. Vadhan. Lecture notes on pseudorandomness. http://eecs.harvard.edu/~salil/cs225, Spring 2007.
• 33: A. C. Yao. Theory and applications of trapdoor functions (extended abstract). In Proc. 23rd FOCS, pages 80--91, 1982.
• 34: D. Zuckerman. Simulating BPP using a general weak random source. Algorithmica, 16(4/5):367--391, Oct./Nov. 1996.
• 35: David Zuckerman, Randomness-optimal oblivious sampling, Random Structures & Algorithms, v.11 n.4, p.345-367, Dec. 1997

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Additional Classification:
  A. General Literature
  A.m MISCELLANEOUS

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Theory