tag:blogger.com,1999:blog-3722233.post116946920570968644..comments2020-09-22T09:42:40.772-05:00Comments on Computational Complexity: Complexity TextbooksLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-1169840829046962482007-01-26T13:47:00.000-06:002007-01-26T13:47:00.000-06:00Here at the University of Minnesota, the grad leve...Here at the University of Minnesota, the grad level computational complexity course taught every few years by the excellent Professor Sturtivant, who lectured almost entirely from memory (including proofs!), we used Sipser and Du and Ko together, mostly for the homeworks. Since I am "just an undergrad" I found Sipser much easier to read, but Du and Ko had a more material. My biggest complaint was that the notations between those two books, the discrete math book, and the algorithms book were all slightly different, which made cross referencing annoying. I don't think that any of the books had legends for the notation, either, preferring that you figure out their conventions from the contexts.<BR/><BR/>Unfortunately I seem to have taken all of the theoretical computer science classes here at the U, so there's nothing left for grad school.Jessehttps://www.blogger.com/profile/08279274005866825218noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169563868301653052007-01-23T08:51:00.000-06:002007-01-23T08:51:00.000-06:00Laci Lovasz's lecture notes from a complexity cour...Laci Lovasz's lecture notes from a complexity course 10 years ago are also online. <BR/><BR/><A HREF="http://research.microsoft.com/users/lovasz/notes.htm" REL="nofollow">http://research.microsoft.com/users/lovasz/notes.htm</A><BR/><BR/>Seemed fine when it was used for a course I took, but haven't compared it to other texts on the subject.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169522668070128812007-01-22T21:24:00.000-06:002007-01-22T21:24:00.000-06:00Yes; the selection of complexity texts has improve...Yes; the selection of complexity texts has improved a lot in the past few years.<BR/><BR/>Regarding the ones mentioned that I've looked at much:<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>Hemaspaandra and Ogihara is targeted at a slightly higher level; I don't believe it's intended for a first course in complexity.<BR/><BR/>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.<BR/><BR/>I don't know that much about the rest, as of yet.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169516015428061472007-01-22T19:33:00.000-06:002007-01-22T19:33:00.000-06:00I am also very happy with what I've read of Arora/...I am also very happy with what I've read of Arora/Barak.<BR/><BR/>Related question--who (online or in print) has got the best problem sets and/or puzzles about or germane to complexity theory? <BR/><BR/>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...Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169497490178084162007-01-22T14:24:00.000-06:002007-01-22T14:24:00.000-06:00It is a shame that no good complexity text exists ...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). <BR/><BR/>Lance, 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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169493201698512442007-01-22T13:13:00.000-06:002007-01-22T13:13:00.000-06:00Why are you not going to write your own textbook a...Why are you not going to write your own textbook anytime soon ?<BR/>Are you too busy writing papers ?<BR/>(and blogging!)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169486855327372552007-01-22T11:27:00.000-06:002007-01-22T11:27:00.000-06:00I also know the upcoming book by Arora/Barak but i...<I> I also know the upcoming book by Arora/Barak but it's still far from complete, would you recommend it for teaching? </I> <BR/><BR/>I 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169486535744923382007-01-22T11:22:00.000-06:002007-01-22T11:22:00.000-06:00Conspicuous by it's absence is ofcourse, Sipser's ...Conspicuous by it's absence <BR/>is ofcourse, Sipser's book.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169481573640518212007-01-22T09:59:00.000-06:002007-01-22T09:59:00.000-06:00Yes, of course. It might be hard though to get ric...Yes, of course. It might be hard though to get rich with a book on complexity theory.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169480214957047862007-01-22T09:36:00.000-06:002007-01-22T09:36:00.000-06:00Can you get rich by writing a book?Can you get rich by writing a book?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169478044071873682007-01-22T09:00:00.000-06:002007-01-22T09:00:00.000-06:00Dexter Kozen's new book on Theoryof Computation (i...Dexter Kozen's new book on Theory<BR/>of Computation (in a lecture like<BR/>format similar to his book on<BR/>algorithms) has a nice collection of<BR/>topics. <BR/><BR/>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=booksAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169476700718043282007-01-22T08:38:00.000-06:002007-01-22T08:38:00.000-06:00There is an excellent book that is in preparation,...There is an excellent book that is in preparation, but in a very mature stage, by Oded Goldreich. It can be found here:<BR/>http://www.wisdom.weizmann.ac.il/~oded/cc-book.htmlAnonymousnoreply@blogger.com