Computational Complexity: A Modern Approach

Front Cover
Cambridge University Press, Apr 20, 2009 - Computers
1 Review
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.
 

What people are saying - Write a review

User Review - Flag as inappropriate

This is a very comprehensive and detailed book on computational complexity. Its target audience are the advanced undergraduates or the first-year graduate students in computational science or a related field. The book has many good and interesting exercises and is very suitable as a textbook. It can be used as a self-study textbook for researchers in other fields as well. However, the notation may not be too familiar to those who have not had any prior exposure to the topics in computational complexity. I am a theoretical Physicist and I consider myself to be fairly well versed in advanced mathematics, but I would probably want to read a book that is at a level just below this one in order to familiarize myself with the notational conventions. Otherwise, it is an extremely interesting and well-organized textbook. 

Contents

Section 1
9
Section 2
38
Section 3
68
Section 4
78
Section 5
106
Section 6
123
Section 7
143
Section 8
172
Section 17
341
Section 18
354
Section 19
361
Section 20
373
Section 21
402
Section 22
411
Section 23
421
Section 24
425

Section 9
201
Section 10
237
Section 11
259
Section 12
270
Section 13
276
Section 14
277
Section 15
286
Section 16
318
Section 25
431
Section 26
498
Section 27
508
Section 28
515
Section 29
531
Section 30
545
Section 31
549

Other editions - View all

Common terms and phrases

About the author (2009)

Sanjeev Arora is a Professor in the department of computer science at Princeton University. He holds a Ph.D. from the University of California, Berkeley and has done foundational work in complexity theory, probabilistically checkable proofs, and approximation algorithms.

Boaz Barak is an assistant professor in the department of computer science at Princeton University. He holds a Ph.D. from the Weizmann Institute of Science.

Bibliographic information