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.
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;
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.
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.
Its great to have such a book online. Thanks!
ReplyDeleteSanjeev'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.
ReplyDeleteAck! 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).
ReplyDeleteLowerbound in one word:
ReplyDeleteThat's a great choice!
It seems that there is a welcomed flood of Complexity Theory Books in the last 5 years or so:
ReplyDelete1. 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 ...
Professor Cai has some interesting notes too:
ReplyDeletewww.cs.wisc.edu/~jyc/book.pdf
Do you mean Trevisan's course notes?
ReplyDeleteYes, 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".
ReplyDeleteThrough the ages, many, if not most, of the textbooks were originated from such course notes.
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.
ReplyDelete