Additional Useful Resources
Complexity Theory
There is no required textbook for this course, but the following books and surveys are suggested if you want to deepen your knowledge on the subject. Throughout the course webpage, we will refer to these resources in the following format: [Authors’ Initials, location in the manuscript]. For instance, to refer to chapter 3 in Arora Barak’s book, we will write [AB, Chapter 3].
- [AB]: Arora, Barak, Computational Complexity: A Modern Approach
- [W]: Avi Wigderson’s new book, Math and Computation
Other Courses
- Prof. Blais’ CS 365
Related Topics
PCP Theorem
Algebraic Complexity Theory
- [R]: Ramprasad et al’s lower bounds survey and references therein.
- [CKW]: CKW'11 survey on the partial derivative method in algebraic complexity theory. Also here.
- [SY]: SY'10 survey on algebraic complexity theory.
- [S1]: Saxena’s first survey on polynomial identity testing.
- [S2]: Saxena’s second survey on polynomial identity testing.
- [BCS]: Buergisser, Clausen, Shokrollahi’s book on algebraic complexity theory.
- [B]: Buergisser’s book on completeness and reductions in algebraic complexity theory.
- [BCSS]: Blum, Cucker, Shub, Smale, Complexity and Real Computation.