Computational Complexity: A Modern Approach

Citation

Arora, S., & Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press.

Chapter Summary

The book has twenty-three chapters in three parts, plus an appendix on mathematical background. A library-catalogue summary of the book calls it a beginning graduate textbook that describes both recent achievements and classical results of complexity theory, requiring essentially no background apart from mathematical maturity, and notes more than 300 exercises with a selected hint set.

Part I: Basic Complexity Classes (Chapters 1–11)

Chapter 1: The computational model - and why it doesn't matter

Sets out the computational model on which everything else rests and argues that the main results do not depend on the specific choice of model.

Chapter 2: NP and NP completeness

The classes P and NP and the theory of NP-completeness.

Chapter 3: Diagonalization

Separation results proved by diagonalization.

Chapter 4: Space complexity

Complexity classes defined by memory use rather than time.

Chapter 5: The polynomial hierarchy and alternations

The polynomial hierarchy as a generalization of NP, and alternation.

Chapter 6: Boolean circuits

Computation by Boolean circuits as an alternative to Turing machines.

Chapter 7: Randomized computation

Probabilistic algorithms and the complexity classes that model them.

Chapter 8: Interactive proofs

Proof systems in which a verifier interacts with a prover.

Chapter 9: Cryptography

Complexity-based foundations of cryptography.

Chapter 10: Quantum computation

Quantum computers as a computational model and the complexity classes associated with them.

Chapter 11: PCP theorem and hardness of approximation: an introduction

An introduction to the PCP theorem and what it implies about the hardness of approximation.

Part II: Lower Bounds for Concrete Computational Models (Chapters 12–16)

Chapters 12–16: Decision trees; Communication complexity; Circuit lower bounds; Proof complexity; Algebraic computation models

This part turns from the abstract classes to restricted models in which lower bounds can actually be proved: decision trees, communication protocols, circuits, proof systems and algebraic models of computation.

Part III: Advanced Topics (Chapters 17–23)

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?

Part III collects the more specialised material: counting problems, average-case complexity, hardness amplification and coding, derandomization, expanders and extractors, the proof of the PCP theorems by Fourier analysis, and the barriers to proving circuit lower bounds.

Appendix A: Mathematical background

The mathematical prerequisites collected in one place.

Key Concepts

Part I: Basic classes

• NP-completeness: the notion of a hardest problem in NP, central to Chapter 2.
• Diagonalization: a proof technique for separating classes.
• Polynomial hierarchy and alternation: layers of complexity above NP.
• Randomized computation, interactive proofs and the PCP theorem: models in which randomness or interaction changes what can be verified.

Part II: Lower bounds

• Concrete models: decision trees, communication protocols, circuits, proof systems and algebraic models in which lower bounds can be proved.

Part III: Advanced topics

• Derandomization and pseudorandomness: removing or replacing randomness.
• Average-case complexity and hardness amplification: complexity beyond the worst case.
• Barriers to circuit lower bounds: why current techniques stop short.

Critical Analysis

Strengths

• Modern selection of topics. Randomized computation, interactive proofs, cryptography, quantum computation, the PCP theorem, derandomization and expanders sit in the same book as the classical material, which is what the title promises.
• Organization by theme. The three parts separate the basic classes, the concrete models in which lower bounds are known, and advanced topics, so that a course can stop after Part I or add selected chapters from Parts II and III.
• Few prerequisites stated. The catalogue summary states that the book requires essentially no background apart from mathematical maturity, and it has more than 300 exercises with a selected hint set.
• Teaching support. The authors' page offers teaching plans for courses based on the book and an errata list.

Limitations

• Demanding for a first exposure. Chapter 1 opens directly with the computational model and Chapter 2 with NP-completeness; readers new to Turing machines and reductions may want a gentler theory of computation text first.
• Selective in Part III. The advanced topics are specialised, and each gets one chapter, so they serve as an introduction rather than a full treatment.
• Broad rather than narrow. Many topics are presented in a single chapter, so researchers in any one of them will need specialised sources.

Where It Fits in the Course

Arora and Barak is the advanced complexity book in this theory of computation course. Sipser's Introduction to the Theory of Computation is the upper-level introduction to automata, computability and complexity, and is the usual preparation. Hopcroft, Motwani and Ullman's Introduction to Automata Theory, Languages, and Computation, Linz and Rodger's An Introduction to Formal Languages and Automata and Kozen's Automata and Computability cover automata and computability in more detail than complexity; MacCormick's What Can Be Computed? grounds the theory in programs. Arora and Barak takes up complexity where these leave off, beginning with the computational model and moving through NP, space, circuits and randomness toward research topics.

How to Use This Book

The book is aimed at advanced undergraduates, beginning graduate students, and researchers in computer science, mathematics and physics who want complexity theory as a reference or for self-study. Mathematical maturity is the main prerequisite; a first course on automata and computability makes Part I easier.

A practical plan:

• Core: Part I, Chapters 1 to 8, which cover the model, NP, diagonalization, space, the polynomial hierarchy, circuits, randomness and interactive proofs.
• Selected from Part I: Chapters 9 to 11 on cryptography, quantum computation and the PCP theorem, according to the course.
• Part II: read after Chapter 6 on circuits; Chapter 14 on circuit lower bounds follows naturally from it.
• Part III: pick chapters by interest; Chapter 23 explains barriers and is a good closing chapter.
• Appendix A for the mathematical background.

Attempt the exercises, using the hint set where needed, and consult the authors' page for teaching plans and errata.