Additional Useful Resources

Books:

There is no required textbook for this course, but the following books are suggested if you want to deepen your knowledge on the subject.

• [AB09] Arora, Sanjeev and Barak, Boaz, Computational Complexity, Cambridge University Press
• [DGH22+] Computers and Intractability: A guide to algorithmic lower bounds
• [GJ79] Garey and Johnson’s Computers and Intractability: a guide to NP-completeness
• [G06] Goldreich’s Computational Complexity: a conceptual perspective
• [MR95] Motwani and Raghavan, Randomized Algorithms, Cambridge University Press, 1995 (QA274.M68)
• [P94] Papadimitriou’s Computational Complexity
• [S92] Sipser’s Introduction To the Theory Of Computation
• [T02] Trevisan, Luca, complexity notes
• [W20] Wigderson, Avi, Mathematics and Computation

Other web resources:

• Prahladh’s and Ramprasad’s complexity course
• Avishay Tal’s complexity course
• Prahladh’s 2020 complexity course
• Salil Vadhan’s complexity course
• Andrej Bogdanov’s computational complexity
• Ryan O’Donnell’s graduate complexity
• Eric Blais’ CS 365
• Eric Allender’s complexity theory lecture notes
• Dieter van Melkebeek’s complexity course
• Madhu Sudan’s complexity theory course
• Chris Umans’ complexity theory course
• Prahladh’s PCP lectures
• Avishay’s pseudorandomness course
• Ryan O’Donnell’s complexity theory’s greatest hits

Further reading:

• History of PCP theorem
• Gil Cohen’s notes on circuit complexity and NEXP not in ACC0
• Oded Goldreich’s complexity materials