Sunday, February 05, 2006

Computational Complexity: A Modern Approach

Sanjeev Arora has posted a draft of his new textbook. A welcome addition to those who wish to learn or teach complexity.


  1. Its great to have such a book online. Thanks!

  2. Sanjeev's book looks great!! I am already thinking of it as a textbook for my grad class on complexity. My only wish is that Sanjeev goes with a publisher who can price the book cheap enough for students to buy.

  3. Ack! As if the phase "to lower bound" didn't sound bad enough, Arora has turned it into a single word "lowerbound" (used as both a noun and a verb).

  4. Lowerbound in one word:
    That's a great choice!

  5. It seems that there is a welcomed flood of Complexity Theory Books in the last 5 years or so:

    1. Arora's book;
    2. Trevisan's online book;
    3. Wegener's Springer book ("Complexity Theory:
    Exploring the Limits of Efficient Algorithms");
    4. "The complexity theory companion" by Hemaspaandra and Ogihara, also from Springer;

    and there might be more that slipped my mind ...

  6. Professor Cai has some interesting notes too:

  7. Do you mean Trevisan's course notes?

  8. Yes, I mean Trevisan's course notes. But it seems that they can serve as a textbook for advanced complexity theory courses too. It's a bit more polished than the standard "course notes".

    Through the ages, many, if not most, of the textbooks were originated from such course notes.

  9. Though this book is quite good, there is one thing I don't like about it, it is the way space complexity is introduced : too late, and too succintely. Most of the complexity results we have now are on space complexity, therefore I think it should have had a greater place in the book.