Compbook»Draft

Computational Complexity: A Modern Approach

Textbook by Sanjeev Arora and Boaz Barak, Cambridge University Press.

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)