What are currently considered to be the best textbooks for complexity? I know the choice is small (PapadimitriouYou have more choices than you think with textbooks by Homer and Selmanis probably still the best even if it is very outdated and somewhat buggy), do most of the lecturers just write their own lecture notes? Is there a set of notes that is especially popular and also used by others. I also know the upcoming book by Arora/Barak but it's still far from complete, would you recommend it for teaching?
,
Hemaspaandra and Ogihara,
Ko
and Du,
Wegener, and several others. Also several
complexity theorists have put their lecture notes on line, quite a
valuable resource. Jin-Yi Cai has the makings of a textbook from his
lecture notes.
The topics and style of a computational complexity course varies from instructor to instructor and no single book would work for all. You really just need to find what best works for you and your class.
I personally don't use a textbook when I teach graduate complexity. I've been so close to the field no book would fit my philosophy unless I write it myself. And that's not going to happen anytime soon.
There is an excellent book that is in preparation, but in a very mature stage, by Oded Goldreich. It can be found here:
ReplyDeletehttp://www.wisdom.weizmann.ac.il/~oded/cc-book.html
Dexter Kozen's new book on Theory
ReplyDeleteof Computation (in a lecture like
format similar to his book on
algorithms) has a nice collection of
topics.
http://www.amazon.com/Theory-Computation-Texts-Computer-Science/dp/1846282977/sr=8-2/qid=1169477787/ref=sr_1_2/104-8886346-5591159?ie=UTF8&s=books
Can you get rich by writing a book?
ReplyDeleteYes, of course. It might be hard though to get rich with a book on complexity theory.
ReplyDeleteConspicuous by it's absence
ReplyDeleteis ofcourse, Sipser's book.
I also know the upcoming book by Arora/Barak but it's still far from complete, would you recommend it for teaching?
ReplyDeleteI used an earlier version of the Arora-Barak book for a course several years ago and I was very happy with it. (The course began with the polynomial-time hierarchy and students had already seen NP-completeness and basic space complexity.) It had a great selection of topics - though not all I wanted to cover, well thought out presentations that did not merely mimic the original papers, and far fewer bugs than more than just one of the published texts listed.
Why are you not going to write your own textbook anytime soon ?
ReplyDeleteAre you too busy writing papers ?
(and blogging!)
It is a shame that no good complexity text exists (I don't consider the Papadimitriou one very good, and anyway it is now outdated), I am glad to see that Goldreich and Barak/Arora are addressing the issue. You can also check out Goldreich's online lecture notes (which are less complete but possibly easier to read than his book if you already know the material).
ReplyDeleteLance, I am curious why you would not use any other book for your course. Is what you teach really that different from, say, what is in Gooldreich's book?
I am also very happy with what I've read of Arora/Barak.
ReplyDeleteRelated question--who (online or in print) has got the best problem sets and/or puzzles about or germane to complexity theory?
It would be nice if paper authors occasionally had the humility to say in the abstract, e.g., 'Theorems 4 and 5 could be proved by an undergrad', just to point people to opportunities to develop their chops. Wishful thinking, though...
Yes; the selection of complexity texts has improved a lot in the past few years.
ReplyDeleteRegarding the ones mentioned that I've looked at much:
Du and Ko is quite fine. My primary complaints, having spent a fair bit of time with it are exercise errata and proof readability. The proofs tended to be not so much terse as much as just having too much internal coupling. I needed to keep track of around twice as many details as necessary to follow the typical proof, requiring a half dozen rereads until I really understood what was going on.
Still a perfectly decent book! I only say a lot about it because the course I took used it. I've since given it a thorough but not quite complete readthrough. It's probably a step up from your typical graduate text. Be particularly wary of definitions contained in exercises, because that's where a lot of the exercise errata lie.
Hemaspaandra and Ogihara is targeted at a slightly higher level; I don't believe it's intended for a first course in complexity.
Someone mentioned Sipser, which is the other way around. It's targeted at an intro-to-theory course that would be a prereq for a course on complexity. Second edition is really nice, but I hear that first edition has excessive errata.
I don't know that much about the rest, as of yet.
Laci Lovasz's lecture notes from a complexity course 10 years ago are also online.
ReplyDeletehttp://research.microsoft.com/users/lovasz/notes.htm
Seemed fine when it was used for a course I took, but haven't compared it to other texts on the subject.