CS 860: Topics in Algorithms and Complexity

Fall 2008: Randomness and Complexity


Reading List

(See the schedule for presentation times.)

Get the journal version when listed. Other versions will probably contain errors and incomplete explanations. (This applies to all papers, not just in this course.)

  1. M. Sipser, "Extractors, Randomness, or Time Versus Space," Journal of Computer and System Sciences 36 (1988) 379-383.
  2. R. Impagliazzo, D. Zuckerman, "How to Recycle Random Bits," in 30th Annual Symposium on Foundations of Computer Science, 1989, pp. 248–253. (See also A. Cohen, A. Wigderson, "Dispersers, Deterministic Amplification, and Weak Random Sources," op. cit., pp. 14–19.)
  3. N. Nisan, A. Wigderson, "Hardness vs Randomness," Journal of Computer and System Sciences 49 (1994) 149–167.
  4. O. Reingold, S. Vadhan, and A. Wigderson, "Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders," Annals of Mathematics 155 (2002) 157-187.
  5. O. Reingold, "Undirected s-t Connectivity in Log Space," in Thirty-Seventh Annual Symposium on Theory of Computing, 2005, 376-375. (See also Electronic Colloquium on Computational Complexity, Report TR04-94.)
  6. I. Dinur, The PCP Theorem by Gap Amplification, J. ACM 54 (2007), art. 12.