Broad Overviews

• Russell Impagliazzo, Computational Complexity since 1980. Invited talk given at FSTTCS 2005, Hyderabad, India (ps).
• Oded Goldreich, A brief overview of complexity theory. (ps).
• Russell Impagliazzo, A personal view of Average-Case Complexity. (ps).

Survey Notes

• Avi Wigderson, Arithmetic Complexity - A survey. Lecture Notes. (ps).
• Manindra Agrawal, Proving Lower Bounds via Pseudo-Random Generators. An invited talk at FSTTCS 2005, Hyderabad, India. (pdf ).

Talks