Computational Complexity: A Modern Approach
- 15h 33m
- Boaz Barak, Sanjeev Arora
- Cambridge University Press
- 2009
This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. More than 300 exercises are included with a selected hint set. The book starts with a broad introduction to the field and progresses to advanced results. Contents include: definition of Turing machines and basic time and space complexity classes, probabilistic algorithms, interactive proofs, cryptography, quantum computation, lower bounds for concrete computational models (decision trees, communication complexity, constant depth, algebraic and monotone circuits, proof complexity), average-case complexity and hardness amplification, derandomization and pseudorandom constructions, and the PCP theorem.
- Contains the modern take on computational complexity as well as the classical
- Covers the basics plus advanced topics that appear for the first time in a graduate textbook
- More than 300 exercises are included
About the Authors
Sanjeev Arora is a professor in the department of computer science at Princeton University. He has done foundational work on probabilistically checkable proofs and approximability of NP-hard problems. He is the founding director of the Center for Computational Intractability, which is funded by the National Science Foundation.
Boaz Barak is an assistant professor in the department of computer science at Princeton University. He has done foundational work in computational complexity and cryptography, especially in developing “non-blackbox” techniques.
In this Book
-
Notational Conventions
-
The Computational Model—And Why It Doesn’t Matter
-
NP and NP Completeness
-
Diagonalization
-
Space Complexity
-
The Polynomial Hierarchy and Alternations
-
Boolean Circuits
-
Randomized Computation
-
Interactive Proofs
-
Cryptography
-
Quantum Computation
-
PCP Theorem and Hardness of Approximation—An Introduction
-
Decision Trees
-
Communication Complexity
-
Circuit Lower Bounds—Complexity Theory’s Waterloo
-
Proof Complexity
-
Algebraic Computation Models
-
Complexity of Counting
-
Average Case Complexity—Levin’s Theory
-
Hardness Amplification and Error-Correcting Codes
-
Derandomization
-
Pseudorandom Constructions—Expanders and Extractors
-
Proofs of PCP Theorems and the Fourier Transform Technique
-
Why Are Circuit Lower Bounds So Difficult?
-
Main Theorems and Definitions
-
Bibliography
