A. Reading List

Following the instructions for Donald Barthelme’s syllabus: Attack these articles “in no particular order, just read them”,

Probabilistic computations: toward a unified measure of complexity
Andrew Yao (1977)

Computational complexity of probabilistic Turing machines
John Gill (1977)

Two theorems on random polynomial time
Leonard Adleman (1978)

Probabilistic decision trees and the complexity of evaluating game trees
Michael Saks and Avi Wigderson (1986)

Complexity classes in communication complexity theory
László Babai, Péter Frankl, and Janos Simon (1986)

Probabilistic communication complexity
Ramamohan Paturi and Janos Simon (1986)

CREW PRAMs and decision trees
Noam Nisan (1991)

Private vs. common random bits in communication complexity
Ilan Newman (1991)

Hard-core distributions for somewhat hard problems
Russell Impagliazzo (1995)

Property testing and its connection to learning and approximation
Oded Goldreich, Shafi Goldwasser, and Dana Ron (1998)

Towards proving strong direct product theorems
Ronen Shaltiel (2003)

Separations in query complexity based on pointer functions
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs (2017)

List currently in progress; more items will be added throughout the term.