Topics
Potential Topics are:
From the book by Arora & Barak, Computational Complexity - A Modern approach, Cambridge University Press:
- Chapter 13: Communication Complexity (plus maybe some additional reading)
- Chapter 15: Proof Complexity (plus maybe some additional reading)
- Chapter 19: Hardness amplification and error correcting codes
- Chapter 21: Pseudorandom constructions
From the book by Hemaspaandra & Ogihara, The Complexity Theory Companion, Springer:
- Chapter 5: The witness reduction technique (Alexander Ikonomou)
Further topics:
- PCP theorem (see Materials page for notes)
- Introduction to Algebraic Complexity Theory (see Materials page for link)