tag:blogger.com,1999:blog-3722233.post113336368553210342..comments2023-05-31T05:44:13.907-05:00Comments on Computational Complexity: The Graduate Complexity CourseLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag: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-1133456765306599852005-12-01T11:06:00.000-06:002005-12-01T11:06:00.000-06:00This brings up a game that Bill Gasarch likes to p...This brings up a game that Bill Gasarch likes to play. We can call it "I can't believe they don't know X" We often play it on undergrad CS majors, but it works for grad students, college graduates, complexity theorists, etc.<BR/><BR/>The idea is that each person states a fact (or theorem, or proof technique, or whatever) that they are shocked, SHOCKED, that the appropriate group doesn't all know. <BR/><BR/>The answers are interesting because there is ALWAYS more than 4 years worth of material in the undergraduate example...Brian Postowhttps://www.blogger.com/profile/04426675383041390587noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133442759522702752005-12-01T07:12:00.000-06:002005-12-01T07:12:00.000-06:00In addition to circuits as Paul suggested, I would...In addition to circuits as Paul suggested, I would add some topics to emphasize the naturalness of the classes, ie some machine-free characterizations, Eg Bellantoni-Cook's recursion system for FP, or some Finite Model Theory characterizations, like Fagin's Theorem. <BR/><BR/>@anonymous: Alternation is still the best way to understand the complexity of many problems. Eg it becomes trivial to see that context-free languages are in P, because the mere definition of a word being generated by a grammar in Chomsky normal form is an alternating logspace algorithm. Also, most problems complete for EXP that I can think of are "really" complete for APSPACE, which just happens to be EXP. Similar for higher classes like EXPSPACE, 2-EXP ...Janhttps://www.blogger.com/profile/01545309650727802288noreply@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