Computational Complexity: A Modern Approach
complexitybook@gmail.com
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 3: Diagonalization
Chapter 4: Space complexity
Chapter 5: The polynomial hierarchy and alternations
Chapter 6: Boolean circuits
Chapter 7: Ranzomized computation
Chapter 8: Interactive proofs
Chapter 9: Cryptography
Chapter 10: Quantum computation
Chapter 11: PCP Theorem and hardness of approximation: an introduction
Part II: Lower bounds for concrete computational models
Chapter 12: Decision trees
Chapter 13: Communication complexity
Chapter 14: Circuit lower bounds
Chapter 15: Proof complexity
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 20: Derandomization
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
General resources on complexity theory
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.
Chapter 1: The computational model and why it doesn't matter
draft (Jan 07)
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.
Chapter 2: NP and NP completeness
draft (Jan 07)
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.
Chapter 3: Diagonalization
draft (Jan 07)
Chapter 4: Space complexity
draft (Jan 07)
Chapter 5: The polynomial hierarchy and alternations
draft (Jan 07)
Chapter 6: Boolean circuits
draft (Jan 07)
Chapter 7: Randomized computation
draft (Jan 07)
Chapter 8: Interactive proofs
draft (Jan 07)
Chapter 9: Cryptography
draft (Jun 08)
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.
Chapter 10: Quantum computation
draft (Jun 08)
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
Chapter 11: PCP Theorem and hardness of approximation: an introduction
draft (Jun 08)
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.
Chapter 12: Decision trees
draft (Jan 07)
Chapter 13: Communication complexity
draft (Jan 07)
Chapter 14: Circuit lower bounds
draft (Jan 07)
See also these lecture notes of Avi Wigderson on lower bounds for constant depth and monotone circuits.
Chapter 15: Proof complexity
draft (Jan 07)
Chapter 16: Algebraic computation models
draft (Jan 07)
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.
Chapter 17: Complexity of counting
draft (Jan 07)
Chapter 18: Average case complexity: Levin's theory
draft (Jan 07)
Chapter 19: Hardness amplification and error correcting codes
draft (Jun 08)
Chapter 20: Derandomization
draft (Jun 08)
Chapter 21: Pseudorandom constructions: expanders and extractors
draft (Jun 08)
For more on expander graphs and their applications, see this survey by Hoory, Linial, and Wigderson.
Chapter 22: Proofs of PCP theorems and the Fourier transform technique
draft (Jun 08)
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.
Chapter 23: Why are circuit lower bounds so difficult?
draft (Jan 07)
Appendix A: Mathematical background
draft (Jun 08)
Web Appendix B: NEXP not in ACC0
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.
draft (December 10)