Name: Computational complexity
ISBN: 9780521424264

Computational complexity

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 Hacker News says

formalsystemAug 2019

There's so much more to CS theory than big O notation and you're in for a treat if you check out any of the below - happy to share more if people are interested.

1. https://www.amazon.com/Computational-Complexity-Approach-San...

2. https://www.amazon.com/Quantum-Computing-since-Democritus-Aa...

3. https://www.amazon.com/G%C3%B6del-Escher-Bach-Eternal-Golden...

4. https://www.amazon.com/Introduction-Theory-Computation-Micha...

thread

charlescearlAug 2019

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 hopcroft ullman from the perspective of understanding what happens in "theoretical computer science" -- I encountered it decades after grappling with hopcroft ullman (so-called "Cinderella book".)

I always find that the best books technically have been those that I take a bite from, think through an idea, maybe check out the references, find a problem to work through, then come back. Here's a quote from the intro that resonated:

"Many parts of the book require hardly any specific prior knowledge and rely mostly on the mathematical maturity needed to take in the definitions and notions introduced. Hopefully, the story telling makes the reading even easier. However, the book (like the field itself) is conceptually dense, and in some parts the concentration of concepts and ideas requires, I believe, slowing down, rereading, and possibly looking at a relevant reference to clarify and solidify the material and its meaning in your mind."

> wigderson is an IAS professor

True, but I think he does a good job of explaining things. This lecture on incompleteness seemed accessible to me https://www.youtube.com/watch?v=0Zmfv3jsiQ0&t=1788s

There's also Sanjeev Arora's book "Computational Complexity: A Modern Approach" https://theory.cs.princeton.edu/complexity/book.pdf

thread

mikevmDec 2013

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 learn about Algorithms and Data Structures and you have a strong math background, then CLRS is the book to get: http://www.amazon.com/Introduction-Algorithms-Thomas-H-Corme...

An undergraduate CS curriculum will mostly cover the parts I-VI of the book (that's around 768 pages) plus a few chapters from the "Selected Topics Chapter" (we covered Linear Programming and String Matching). Mind you, this book is very theoretical, and all algorithms are given in pseudocode, so if you don't know any programming language, you might have to go with a an algorithms textbook that is more practical. In my DS course we had to implement a Red-Black tree and a binomial heap in Java, and in my Algorithms course we only wrote pseudocode.

Maybe Sedgewick's (Knuth was his PhD advisor!) "Algorithms (4th ed)" will be a better choice for a beginner, as it shows you algorithm implementations in Java: http://www.amazon.com/Algorithms-4th-Edition-Robert-Sedgewic... (If you decide to go this route, you might as well take his two Algorithms courses on Coursera, they will really help).

There are also a bunch of Python-based introductions to computer science which have a broader focus than just teaching specific data structures and algorithms. Some of them emphasize proper program design, debugging and problem solving. I haven't read any of them, so I can't vouch for them, but here are a few of the more popular ones:

* http://www.amazon.com/Introduction-Computation-Programming-U...

This book was written to go along with John's edX course: https://www.edx.org/course/mitx/mitx-6-00-1x-introduction-co...

* http://www.amazon.com/Python-Programming-Introduction-Comput...

Oh and btw, there's also the Theory of Computation, which is a major part of CS theory. Here are a few MOOCs and recommended books on the subject:

MOOCS:

* https://www.coursera.org/course/automata

* https://www.udacity.com/course/cs313

Books:

* http://www.amazon.com/Introduction-Theory-Computation-Michae...

Sipser's book is probably the best introduction to the theory of computation, and I believe its last chapter deals with Complexity theory as well.

* http://www.amazon.com/The-Nature-Computation-Cristopher-Moor...

I loved this book very much. It has a very informal and conversational style (don't let it fool you, the problem sets can be HARD).

* http://www.amazon.com/Computational-Complexity-A-Modern-Appr...

Once you are familiar with some computation models, its time to study computational complexity and this is one of the best books on the subjects. It is used both for graduate and undergraduate courses.

thread