
Computational complexity
Sanjeev Arora · 2007
Programming and computer science › Algorithms and coding interviews
#10,779 most recommended
Hacker News
3
mentions by 3 people · top 64% of 15,732 books
Open Library
—
No ratings yet
7 want to read
Wikipedia
—
No article yet
About the book
This book is a graduate-level textbook on computational complexity theory, co-written by Sanjeev Arora and Boaz Barak. It starts with Turing machines and the basic time and space complexity classes, then covers probabilistic algorithms, interactive proofs, cryptography, and quantum computation. It requires mathematical maturity rather than prior background in the field, and it includes over 300 exercises with a selected hint set. The book does not advance a single thesis. It treats complexity theory as organised around a few questions: which problems admit efficient algorithms, how randomness, interaction, and quantum resources change what is efficiently computable, and why proving lower bounds is so hard. It presents recent results such as the PCP theorem and derandomization through pseudorandom constructions as revising earlier answers, and it develops lower-bound techniques for restricted models like circuits and decision trees as partial progress toward P versus NP.
Written by Claude from what it knows of this book.
What Hacker News says 100% recommend · 0% critical
In the commenters’ own words
What do you want to learn? Programming or CS? CS is more than just programming, and CS theory is more than just Algorithms & Data Structures. If you want to…
Hey sorry, point taken. I have read chapters and was excited about it, but I see your point. Thanks for the suggestions. I found the book more readable than…
What Open Library readers say
No Open Library reader has rated it yet.
- 7 want to read
- 0 reading
- 0 have read
What critics say, via Wikipedia
No Wikipedia article about this book yet, so no critics to quote.
Reddit communities — coming later
The threads it came up in
Details
- First published
- 2007
- ISBN
- 9780521424264
- Editions known
- 12 at Open Library
- Open Library
- OL13759314W
511.3/52Computational complexityComputer TechnologyElectronic data processingNonfictionQa267.7 .a76 2009
Read next: its neighbours on the mosaic
Python programmingJohn M. Zelle · 2003 · recommended by 6 people · loosely similar by subject
Introduction to the theory of computationMichael Sipser · 1997 · recommended by 66 people · similar by subject and what people say about it
Quantum Computing Since DemocritusScott Aaronson · 2013 · recommended by 73 people · similar by subject and what people say about it
How to Think About AnalysisLara Alcock · 2014 · recommended by 15 people · similar by subject and what people say about it
Introduction to AlgorithmsThomas H. Cormen · 1990 · recommended by 274 people · similar by subject and what people say about it
The nature of computationCristopher Moore · 2009 · recommended by 10 people · similar by subject and what people say about it
Theory of computationMichael Sipser · 2007 · recommended by 14 people · similar by subject and what people say about it
ComputationMarvin Minsky · 1967 · recommended by 5 people · similar by subject and what people say about it
Computational complexityChristos H. Papadimitriou · 1994 · recommended by 7 people · similar by subject and what people say about it
Complexity and real computationLenore Blum · 1998 · recommended by 2 people · similar by subject and what people say about it
Computability and complexityNeil D. Jones · 1997 · recommended by 1 person · similar by subject and what people say about it
Practical linear algebraGerald E. Farin · 2013 · recommended by 5 people · loosely similar by subject
Computers and intractabilityMichael R. Garey · 1979 · recommended by 5 people · similar by subject and what people say about it
An introduction to Kolmogorov complexity and its applicationsMing Li · 1993 · recommended by 5 people · similar by subject and what people say about it
Introduction to automata theory, languages, and computationJohn E. Hopcroft · 1979 · recommended by 24 people · similar by subject and what people say about it
Computer scienceJ. Glenn Brookshear · 1985 · recommended by 8 people · similar by subject and what people say about it
A Computational Introduction to Number Theory and AlgebraVictor Shoup · 2005 · recommended by 4 people · similar by subject and what people say about it
Algorithm designJon Kleinberg · 1922 · recommended by 30 people · similar by subject and what people say about it
Yet another introduction to analysisVictor Bryant · 1990 · recommended by 4 people · loosely similar by subject
Quantum Computer ScienceN. David Mermin · 2007 · recommended by 11 people · similar by subject and what people say about it
Think ComplexityAllen B. Downey · 2012 · recommended by 11 people · similar by subject and what people say about it
Elements of the Theory of ComputationLewis, Harry R., and Christos H. Papadimitriou · 1981 · recommended by 5 people · similar by subject and what people say about it
Quantum computing for computer scientistsNoson S. Yanofsky · 2008 · recommended by 10 people · similar by subject and what people say about it
All of StatisticsLarry Wasserman · 2004 · recommended by 40 people · similar by subject and what people say about it