home | draft and extras | teaching plans | errata
This page contains early drafts of the book, as well as links to additional relevant material available online. See this page for links to courses using this book.
Part I: Basic Complexity Classes
Chapter 1: The computational model and why it doesn't matter
Chapter 2: NP and NP completeness
Chapter 5: The polynomial hierarchy and alternations
Chapter 7: Ranzomized computation
Chapter 10: Quantum computation
Chapter 11: PCP Theorem and hardness of approximation: an introduction
Part II: Lower bounds for concrete computational models
Chapter 13: Communication complexity
Chapter 14: Circuit lower bounds
Chapter 16: Algebraic computation models
Part III: Advanced topics
Chapter 17: Complexity of counting
Chapter 18: Average case complexity: Levin's theory
Chapter 19: Hardness amplification and error correcting codes
Chapter 21: Pseudorandom constructions: expanders and extractors
Chapter 22: Proofs of PCP theorems and the Fourier transform technique
Chapter 23: Why are circuit lower bounds so difficult?
Appendix A: Mathematical background
Web Appendix B: NEXP not in ACC0
Many complexity theorists put their research papers on their home page and/or post them on Internet archives such as the Electronic Colloquium on Computational Complexity (ECCC) or the Arxiv.
There are many excellent lecture notes for complexity theory on the web. A partial list includes Irit Dinur, Steven Rudich and Manuel Blum, Madhu Sudan, Luca Trevisan (see also his blog), Russel Impagliazzo , Chris Umans, Oded Goldreich (see also his book ), Uri Feige & Ran Raz, Moni Naor, Valentine Kabanets , Dieter van Melkebeek, Muli Safra
Some surveys on complexity can be found on the bulletin of the EATCS (other sources of surveys include "SIGACT news" and "foundations and trends of theoretical computer science", but they seem not to be freeely available online).
There are several important topics connected to computational complexity that we cover in the book only briefly or not at all. One area that is completely missing is computational learning theory. See this course by Avrim Blum and this text by Kearns and Vazirani for more.
This chapter only briefly touched on computability theory and Godel's incompleteness theorem. Besides the textbooks we cite, Aaronson's course contains some additional material.
See the NP optimization problems compendium for the NP-completeness status of many important optimization problems.
See also David Johnson's classical columns on NP completeness.
Many relevant links can be found from the web page of Boaz's cryptography course. Some early drafts of Goldreich's book are available here. Judging from the authors and table of contents, the upcoming book by Boneh and Shoup looks extremely good.
Many topics that we did not cover, including quantum error correction, quantum black-box lower bounds, and the ``Quantum Cook-Levin Theorem'', can be found on Umesh Vazirani's lecture notes
Approximation algorithms are covered in many texts and online lecture notes, including Princeton's COS 521 Advanced Algorithms course (see this page). More resources on the PCP Theorem are linked below in the notes to Chapter 22.
See also these lecture notes of Avi Wigderson on lower bounds for constant depth and monotone circuits.
Algebraic complexity is a large and beautiful area, and we only mention a few of its results in this chapter. Some more material can be found in these lecture notes of Avi Wigderson.
For more on expander graphs and their applications, see this survey by Hoory, Linial, and Wigderson.
One thing we didn't include is a proof of the parallel repetition lemma. The original proof by Raz was simplified by Holenstein. See also this writeup of the simplified proof.
For more on PCP and hardness of approximation, see these lecture notes by Guruswami and O'Donnell and these notes by Irit Dinur. Ryan O'Donnell also has online lecture notes for his course on Fourier analysis of Boolean functions, see also lecture notes by Guy Kindler, Subhash Khot, Irit Dinur and Ehud Friedgut, Nati Linial, Dieter van Melkebeek, and Elchanan Mossel.
Very recently, Ryan Williams showed that NEXP is not contained in ACC0, thus resolving Forntier 2.1 from Chapter 14 of the book. We will add this exciting result to future versions of our book. In the meantime added this web appendix containing a full proof of the result (building on results presented in previous chapters) so people can teach it in courses based on the book.