Additional Useful Resources

Algebraic 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 Ramprasad et al’s survey, we will write [R, Chapter 3].

• [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.

Related Topics

Complexity Theory

• [W]: Avi Wigderson’s new book, Math and Computation
• History of PCP theorem

Real Algebraic Geometry & Connections

• [BPT] Blekherman, Parrilo, Thomas, Semidefinite Optimization and Convex Algebraic Geometry