tag:blogger.com,1999:blog-3722233.post113336368553210342..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: The Graduate Complexity CourseLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-1133576001249461912005-12-02T20:13:00.000-06:002005-12-02T20:13:00.000-06:00"4 years worth of material" is a pretty ambiguous ..."4 years worth of material" is a pretty ambiguous metric.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133408294067550062005-11-30T21:38:00.000-06:002005-11-30T21:38:00.000-06:00At the risk of sounding pushy, I truly enjoyed the...At the risk of sounding pushy, I truly enjoyed the first podcast with Bill Gasarch and think that this topic presents the opportunity for another.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133403267054233512005-11-30T20:14:00.000-06:002005-11-30T20:14:00.000-06:00Lance, I'm curious why you suggest teaching altern...Lance, I'm curious why you suggest teaching alternation and Toda's theorem. I thought alternation was "passe", except maybe as a way to introduce the PSPACE-complete problem of quantified boolean formulae. As for Toda's theorem, I know it is considered central but I never quite understood why...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133402623844641392005-11-30T20:03:00.000-06:002005-11-30T20:03:00.000-06:00Papadimitriou's '94 text is fun and readable (thou...Papadimitriou's '94 text is fun and readable (though with a slightly daunting coverage of logic) and covers all but the last two topics (it describes their importance). In fact, my worry is that for anyone who got hooked on complexity thru that book (like me), the proposed course is unexciting. <BR/><BR/>Paul's suggestions sound good, though the case has to be made for existing circuit bound techniques having relevance to the project of finding really good ones (though the parity bound has e.g. the PH separation oracle applications to recommend itself).<BR/><BR/>I'll just suggest relativization be added. Complexity theorists need to learn how to use it; other students need some explanation why this course doesn't answer most of the questions it raises.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133401492430593852005-11-30T19:44:00.000-06:002005-11-30T19:44:00.000-06:00Do you remember the list of topics of the 1985 Har...Do you remember the list of topics of the 1985 Hartmanis course and the 1986 Sipser course?Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133395074475162552005-11-30T17:57:00.000-06:002005-11-30T17:57:00.000-06:00You did not comment on which the best books are to...You did not comment on which the best books are to follow for the material in this course (if doing a self-study). Could you comment on that as well?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133378721401641082005-11-30T13:25:00.000-06:002005-11-30T13:25:00.000-06:00The lack of circuit complexity in your list misses...The lack of circuit complexity in your list misses out on an entire way of looking at complexity problems and any lower bound technique other than diagonalization. I think that any such complexity course should at least expose students to the circuit complexity approach especially since it is the main way to understand low level complexity classes. I would add to your list:<BR/><BR/>* Circuit complexity classes: NC, AC^0, AC^0[p], TC^0, P/poly<BR/>* Parity not in AC^0 and/or Mod_p not in AC^0[2]<BR/>* to tie things in I would include NP not in P/poly unless PH collapses although this isn't essential<BR/>*(the circuit view of PH in P^PP is also particularly convenient).<BR/><BR/>When I last taught such a course I also taught:<BR/>* #P-completeness <BR/>* IP, AM, MA<BR/>* Graph Isomorphism is not NP-complete unless PH collapses.<BR/>* Time-space tradeoff lower bounds for SAT<BR/>* Clique requires exponential size monotone circuits.<BR/><BR/>Paul BeameAnonymousnoreply@blogger.com