Computational Complexity: A Modern Approach

by Sanjeev Arora, Boaz Barak

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.

Genres: Computer Science, Mathematics, Science, Textbooks, Programming, Computers, Reference

594 pages, Hardcover

First published December 13, 2007

Reviews

[Nick Black · Rating 4 out of 5]

Amazon 2009-06-17. Wow, this is *REALLY GOOD* so far, definitely the best of several computational complexity books I've ever read (as the first major publishing event in complexity theory since Aaronson's development of the Complexity Zoo, perhaps there was a higher bar to leap). Seventeen thirty-two, personal note: my signature lifts a quote from the Complexity Zoo:

Nondeterministic Polynomial-Time: The class of dashed hopes and idle dreams...

The book was clearly designed with the assumption that Sipser's modern classic Introduction to the Theory of Computation would be used as an undergraduate precursor; besides referencing Sipser several times early on (and his role heading up MIT's Math department, a group the authors are -- from the Foreward -- definitely good pals with (the authors themselves hail from Princeton, where I had no idea but Brian Kernighan and Robert Sedgewick are still faculty (of course I knew Andrew Appel, Edward Felten, and Robert Tarjan were still there, and Andrew Yao/Richard Lipton's emeritus status (but we've got Lipton now, motherfuckers!)))). The book takes off almost directly from where Sipser's study of complexity ends, with a deep study of p≤ polynomial-time Karp reducibility (well, actually it starts with deterministic TM's, but as I've studied the 7-parameter TM formalism since I was thirteen or so, I didn't look at Chapter 1 too closely (I *do* applaud their Claim 1.6: single-tape simulation of k-tape TM's in time 5kT(n)^2 -- this kind of rigorous, strong presentation is welcomed -- and ESPECIALLY the early presentation of oblivious Turing Machines (those which care only about the input length, not the input content), as this simplifies many a proof later on (most authors, if they introduce OTM's at all, do so only as a curiousity and not as a fundamental proof mechanism))). The heavy emphasis throughout on the dual miracles of randomization and modern crypto (including more advanced topics like derandomization, the probabilistic complexity classes, pseudorandomization and hardness amplification) will hopefully result in these topics being more deeply embedded within classical theory classes, as they should be. Furthermore, being placed (for the first time?) on the same footing as automata and the Hierarchy means that relevant issues are addressed throughout -- the implication that P == NP, for instance, would mean that nothing is to be gained from randomized algorithms, was entirely new to me *despite* having taken Lipton's Randomized Algorithms class and having read both of the two major books on the subject (Motwani + Raghavan and Mitzenmacher + Upfal). I can fairly say that realizing this obvious truth blew my mind.

The book has wonderful quotes heading each chapter, which I just can't say enough about. Computer scientists don't know nearly enough of the rich history of their study (I'm regularly scandalized when I run into graduate students -- not the ladies and man-ladies in things like Human-Computer Interaction, but real apprentice computer scientists -- who don't know the names of Church, Rabin, Aho, Hamming and Hoare. I want to punch these ingrates in the face), and things like this can only help. The bibliography and citations are kind of sparse, but the important ones are there, and the authors are as current with the literature as one would hope (I was pleased to see the newly-seminal AKS2004 referenced early on).

Be sure to check out section 2.7.3, "The P == NP Utopia", for a special treat -- coverage of the implications of that most foul heresy, the majority of which I'd heard elsewhere, but only as single, whispered perversions -- with a look forward to chapter 5, its coverage of the polynomial hierarchy, and a surprise or two regarding MIN-EQ-DNF (btw, if you've never read it, Aaronson's tongue-in-cheek "Polynomial Hierarchy Collapses" is one of the funniest things ever written).

One comment -- the exercises, so far, are both really fucking weird and really fucking difficult. I am not sure I'd want to use this book's problem sets as self-study; classics like Papadimitriou are still the best in this arena, IMHO.

I'm not yet done, and this might yet get its fifth star -- we'll see. What is certain, however, is that there is a new standard reference for undergraduate and graduate students, researchers and professionals interested in the majestic sweep of complexity theory, and its authors are Sanjeev Arora and Boaz Barak.

[Miquel · Rating 5 out of 5]

Com que aquí estem en petit comitè, us confesso (ho negaré en seu judicial) que poder saludar a en Boaz el desembre passat em va fer il·lusió.

[Pablo · Rating 5 out of 5]

An excellent book on computational complexity, covering a wide range of topics that I haven't found discussed in other books. It is useful both as reference material and as a self-learning textbook. I haven't read all the chapters in detail (I was more interested in Parts I and III).
The exercises are interesting and have hints and the chapter notes are full of really useful references for further reading

[Shehryar Saroya · Rating 2 out of 5]

Read it to get the details. Sort of overshadowed, for me, by Moore's "Nature of Computation"

[Bojan Tunguz · Rating 5 out of 5]

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.

[Ayush Bhat · Rating 5 out of 5]

The only book around that teaches the lower bound theory well.

[Yunge Hao · Rating 5 out of 5]

It's better than Sipser's.

[Tanner Duve · Rating 4 out of 5]

Good graduate text on complexity theory. Of all the complexity books out there I’d choose this one. Gives a very thorough survey of the field, starts with a basic review of Turing machines, NP-completeness, etc. Nice intro to some of the real topics in complexity: polynomial hierarchy, circuit complexity, interactive proofs, cryptography, etc.. Also includes a lot of advanced topics like derandomization and quantum computing. Definitely requires some math background - to understand everything in the book you need to know probability, linear algebra, and some group/ring theory. Each concept is accompanied by motivating commentary which makes it enjoyable, and chapters open with quotes providing nice historical context. The exercises are freaking hard but pedagogically effective. Overall a pretty hardcore book, definitely for grad students, but densely packed with information. Learned a lot from it.

[Klickup · Rating 5 out of 5]

This book broke my neck and I loved it. Essential if you are interested in theoretical CS.

[Huy · Rating 5 out of 5]

great book covering a lot of modern topics. For a long time there was no textbook for material beyond Sipser's book but this book nicely fits in this gap and offers enough material for a graduate level course and more for personal exploration.

[Moukarram · Rating 5 out of 5]

A great book helped me throught the computational complexity subject back when it was in the draf version. My name appears on page 12 ;)

[Thomas · Rating 4 out of 5]

A very comprehensive book on complexity. It is quite understandable and goes far beyond understanding the P = NP problem (which was my initial goal).

[Divyanshu Shende · Rating 5 out of 5]

Excellent Book. Very well written. Contained a few typos in my edition but nevertheless, generates an interest in the subject.

[MindOverMatter · Rating 5 out of 5]

Loved it!

[DJ]

recommended by Scott Aaronson as an advanced investigation into complexity

[Gerrit G.]

We worked through most of this book in a seminar for grad students, when it was new. Don't think it is for beginners in (theoretical) computer science, but it is decent for an extended intro into complexity theory.