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.)
-
M. Sipser,
"Extractors, Randomness, or Time Versus Space," Journal of
Computer and System Sciences 36 (1988) 379-383.
- 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.)
-
N. Nisan, A. Wigderson, "Hardness vs
Randomness," Journal of Computer and System Sciences
49 (1994) 149–167.
-
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.
-
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.)
-
I. Dinur, The PCP Theorem by Gap Amplification, J. ACM
54 (2007), art. 12.