tag:blogger.com,1999:blog-3722233.post7456446843082393759..comments2023-09-30T21:44:03.907-05:00Comments on Computational Complexity: Graduate Complexity Theory CourseLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-75683383729074556182007-11-14T02:57:00.000-06:002007-11-14T02:57:00.000-06:00Hi Bill, I've been reading the comments on this p...Hi Bill,<BR/> I've been reading the comments on this post, and am actually helping design a complexity reading group based on your structure, and the comments on the post. So thanks a lot for bringing this topic up.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88567047119082313462007-08-19T13:33:00.000-05:002007-08-19T13:33:00.000-05:00Anon 5,for Parity not-in Ac^0 via polynomials Voll...Anon 5,<BR/><BR/><I>for Parity not-in Ac^0 via polynomials </I><BR/><BR/><BR/>Vollmer's "Introduction to Circuit Complexity" has a detailed and elementary exposition of the polynomial method for AC^0. It's full of details, lengthy and highly clear.<BR/><BR/>Kranakis & Clote book from 2002, also has the polynomial method for AC^0 (with mod q gates). It's very concise but quite unclear.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61026806637536287262007-08-16T14:17:00.000-05:002007-08-16T14:17:00.000-05:00This is Anon 3 == Anon 14:Bill says:Anon 3: Which ...This is Anon 3 == Anon 14:<BR/><BR/>Bill says:<I><BR/>Anon 3: Which results are `If pigs can whistle?'<BR/>GI NPC --> PH collapses is not.<BR/>PARITY SAT in P --> NP=R is not--- especially given<BR/>Valiants recent results on Planar-Sat-Mod-7.<BR/>Clique-approx --> P=NP is not--- there ARE NPC problems<BR/>that can be approximated. </I><BR/><BR/>Really? I am not saying that any of this is "likely" or "unlikely" (though I do realize that in general, a whistling pig in a whistling pig theorem is considered to be an unlikely hypothesis). We have as much clue into the truth/falsehood of "GI is NPC" or "ParitySAT in P" or "Clique can be approximated" or "PH collapses" or "P = NP" as we do about whether pigs <I>could</I> whistle.<BR/><BR/>My point (if you were wondering whether I had one) is this: what's the point of teaching these implications in a first course in complexity theory, esp. one for non-theorists? After having worked in complexity for several years, I feel that these results add to the richness of our field and build a rather delicate fabric of interrelationships among complexity classes, but if you ask me what a result like "GI NPC ==> PH collapses" says (in isolation), I'd be hardpressed to say anything meaningful.<BR/><BR/>In other words, I suspect that these results give little or no takeaways for general CS students.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29838395253745537182007-08-16T11:58:00.000-05:002007-08-16T11:58:00.000-05:00Anons 5 and 7:for Parity not-in Ac^0 via polynomia...Anons 5 and 7:<BR/><BR/>for Parity not-in Ac^0 via polynomials, look up "spielman complexity scribe parity polynomial" on google and see top two results.<BR/><BR/>Papadimitriou's book has a very accessible version of Fagin's theoremAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2701613847772458132007-08-16T11:17:00.000-05:002007-08-16T11:17:00.000-05:00I think teaching randomness is very important. Tha...I think teaching randomness is very important. That may also be a good excuse the teach them expanders, which of course are everywhere. (Dinur's PCP proof may be another excuse)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12764282569711653982007-08-16T10:53:00.000-05:002007-08-16T10:53:00.000-05:00An "if pigs can whistle, then horses can fly" resu...An "if pigs can whistle, then horses can fly" result can be viewed as "if horses cannot fly, then pigs cannot whistle" which may look more convenient.<BR/><BR/>What is the original quote by the way? Shouldn't it involve pigs and donkeys instead? :)Mahdihttps://www.blogger.com/profile/12382401759237060260noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91040147023573996432007-08-16T10:03:00.000-05:002007-08-16T10:03:00.000-05:00Thanks for all the comments.Here are some response...Thanks for all the comments.<BR/>Here are some responses.<BR/><BR/><BR/>Anon 1:<BR/>Toda's theorem VERSUS IP=PSPACE.<BR/>Toda's theorem tells us something interesting<BR/>about a natural problem: #SAT is harder than<BR/>we thought. IP=PSPACE is a great result but<BR/>does not easily lead to results on classifying<BR/>difficulty of problems.<BR/><BR/>Suresh: Some of your points I DO cover, some I do not.<BR/>I will do WHY P? TRUST BUT VERIFY, IP (while doing GI stuff).<BR/>Some I will not.<BR/><BR/>Anon 3: Which results are `If pigs can whistle?'<BR/>GI NPC --> PH collapses is not.<BR/>PARITY SAT in P --> NP=R is not--- especially given<BR/>Valiants recent results on Planar-Sat-Mod-7.<BR/>Clique-approx --> P=NP is not--- there ARE NPC problems<BR/>that can be approximated. Mahaney and Karp-Lipton certainly<BR/>are pigs-whistle; however, I need Karp-Lipton to do GI stuff.<BR/>Mahaney could be omitted, but its a nice intro to sparse sets<BR/>and a nice thing to see before Karp-Lipton.<BR/><BR/>Anon 3: Teaching the full proof of PCP to non-theorists does not<BR/>have a good time/benefit tradeoff.<BR/><BR/>Anon 3: ``AC_0 is a must-do''- alas there are too many ``must-do's''<BR/>so we can't to them all.<BR/>Derrick (commenter 4) got it right when he pointed out that<BR/>to do all he wants to do would take 3 semesters.<BR/><BR/>Paul Beame- YES, PSPACE-complete results may be a good thing to do.<BR/>Immerman-Sc.. is already in the course- note I have NL=co-NL.<BR/><BR/><BR/><BR/>Upshot of all of your comments- I will try to put in some of<BR/>Suresh's teaching tips and motivation, and as Beame suggests,<BR/>PSPACE-complete problems. Once I finish the course I'll see<BR/>what seemed to work and not work<BR/>(e.g., I may find that doing VV is good but doing Toda is not<BR/>good for time/benefit tradeoffs) and consider putting in<BR/>PARITY and CLIQUE as they are, as one of the Anon said,<BR/>the only two lower bounds we know.<BR/><BR/> Bill GasarchGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87060961285729453482007-08-16T02:58:00.000-05:002007-08-16T02:58:00.000-05:00Please explain; I always thought Miller-Rabin was ...<I>Please explain; I always thought Miller-Rabin was an excellent example of a coRP (or RP, depending on your language) algorithm.</I><BR/><BR/>I did, briefly. This all depends where the witness values you test come from. If you test all numbers from 1 to log^2 n, you get a deterministic algorithm which is polynomial time conditional on the generalized Riemann hypothesis. If you test a random value, you get an RP algorithm. You can also get a P/poly algorithm by supplying the witnesses as the advice string, since there is a small set of witnesses that works for every input up to a given length. The proof of this follows essentially the same lines as the BPP in P/poly proof - if for every composite number 3/4s of all lesser numbers are witnesses, then necessarily all numbers up to a certain size have some finite base of polynomial size in common. Some of these advice strings have been explicitly determined for some small input sizes (up to about 341 x 10^12):<BR/><BR/>http://primes.utm.edu/prove/prove2_3.html<BR/><BR/>This has some practical use as a very efficient deterministic primality test for small numbers (without the unreasonable space requirements a trivial lookup table would have).D Coetzeehttps://www.blogger.com/profile/05407492273389264037noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17207049295279797632007-08-15T20:40:00.000-05:002007-08-15T20:40:00.000-05:00The people taking my course will largely not be do...<I>The people taking my course will largely not be doing theory. Hence I want them to come away knowing some very definite things.</I><BR/><BR/>Many of them will encounter PSPACE-complete problems in their research. They should understand what this is all about and Savitch's Theorem is a natural/necessary accompaniment. While you're at it, Immerman-Szelepcsenyi is very definite, actually pretty easy to teach, and non-theory students enjoy it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35837287053904726082007-08-15T19:36:00.000-05:002007-08-15T19:36:00.000-05:00A good writeup of Fagin's theorem, including visua...A good writeup of Fagin's theorem, including visual aids, appears in Immerman's book Descriptive Complexity.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62730669313416339432007-08-15T19:00:00.000-05:002007-08-15T19:00:00.000-05:00For that matter, does anyone know a good writeup o...For that matter, does anyone know a good writeup of Fagin's theorem? It doesn't seem to appear in the standard textbooks...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69309956465211289352007-08-15T18:55:00.000-05:002007-08-15T18:55:00.000-05:00The Miller-Rabin test provides an excellent nontri...<EM>The Miller-Rabin test provides an excellent nontrivial example for a P/poly algorithm</EM><BR/><BR/>Please explain; I always thought Miller-Rabin was an excellent example of a coRP (or RP, depending on your language) algorithm.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38350707496231049022007-08-15T18:38:00.000-05:002007-08-15T18:38:00.000-05:00Can anyone suggest a good reference (maybe online ...Can anyone suggest a good reference (maybe online lecture notes?) for <EM>"PARITY not-in AC^0 ... with a pretty polynomial based proof"</EM>?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60749283077185005742007-08-15T17:37:00.000-05:002007-08-15T17:37:00.000-05:00At some point, I'd project a screenshot of the tab...At some point, I'd project a screenshot of the table of contents of Complexity Zoo up on the wall, just to get the point across that there is a *lot* of stuff you're leaving out.<BR/><BR/>I think that as well as proving lots of easy results, it also gives more idea of the scope of things to at least state lots of harder results along the way. For example, I'm fond of the result that DSPACE(f(n)) is strictly contained in DSPACE(f(n)) for space-constructible f(n) ("On time versus space") and it fits in with discussion of the hierarchy theorems. It's good to do PARITY not in constant depth, CLIQUE not in monotone P, and inapproximability results because, well, you might as well cover all the lower-bounds we know. Must mention the nebulous status of factoring, GI, and (down inside P) GCD.<BR/><BR/>I would emphasise an analogy between log-space and "in-place algorithms" and mention the L=P and L=NL problems, and that Savitch's theorem implies NL in L^2. I also think L=SL is worth stating, but I would formulate it as "you can do undirected graph connectivity in log space, and look, here's a bunch of problems that log space reduce to it" (not even mentioning symmetric TMs or expanders). I would just state Toda's theorem rather than prove it. I also would talk about EXPTIME-complete a bit, since it's nice to have some problems that we *know* are outside P. This fits in with Mahaney's theorem because of NP - P containing sparse languages being equivalent to EXPTIME != NEXPTIME (and might as well mention that sparse P-complete languages imply L = P while you're at it). Interactive protocols have to be visited, but I would just state IP = PSPACE (and MIP = NEXPTIME too).<BR/><BR/>When talking about NP-complete problems, I would mention the bounded Post correspondence problem and an automata problem like regular expression inequivalence to provide a connection to former education on computability and automata theory.<BR/><BR/>The primality problem, besides being of interest itself in its inexorable descent through the classes, provides a good context to frame lots of other topics. It's a good place to introduce randomness and quantum computing (Shor's algorithm). The Miller-Rabin test provides an excellent nontrivial example for a P/poly algorithm - the advice string supplies the witnesses to test, which leads naturally into BPP contained in P/poly.<BR/><BR/>Oh, and alternating TMs and their characterization of P, PH, and PSPACE are handy. And just a bit of descriptive complexity, to tie it into logic - Fagin's theorem and a discussion of this picture:<BR/><BR/>http://www.cs.umass.edu/~immerman/descriptive.jpg<BR/><BR/>Things I wonder: should PP be introduced in the context of randomness and BPP, or in the context of nondeterminism and #P? To what extent should the beliefs that P != NP, L != P, P = BPP, and the noncollapse of the polynomial hierarchy be justified? How far to delve into approximation algorithms (talk about PTASs and APX-completeness?) There's no need to go into every oracle result under the sun, but it's really important to explain that there's no relativizing proof for P = NP. Hrm, I think I've used up about 3 semesters. :-PD Coetzeehttps://www.blogger.com/profile/05407492273389264037noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44092825201400349642007-08-15T15:45:00.000-05:002007-08-15T15:45:00.000-05:00For a course intended to convey some "definite thi...For a course intended to convey some "definite things", 3 of the 6 listed topics have the "if pigs can whistle, then horses can fly" flavor :-)<BR/><BR/>More quibbles/comments:<BR/><BR/>While your point about abstract vs. concrete is fair enough, I think PARITY not-in AC^0 is a must-do result (esp. with a pretty polynomial based proof). AC^0 is quite "abstract", esp. because of the connection to first-order logic. Speaking of logic, Fagin's theorem is another true gem in complexity theory that must be included.<BR/><BR/>I don't understand why you say "don't even try" for the PCP theorem. Dinur's proof makes it extremely teachable - if a bit ambitious to teach to non-theorists.<BR/><BR/>I'd leave out Mahaney, Karp-Lipton, Valiant-Vazirani... and include Parity not-in AC^0, Fagin's theorem, IP=PSPACE, PCP Theorem, and Fortnow+ theorem on time-space lower bounds for SAT... and perhaps include a "showcase" section on four problems that have been at the heart of much of the last two decades' work in complexity theory (randomness vs. determinism):<BR/>Primality (RP v P), Undirected Graph Connectivity (RL v L), Graph NonIsomorphism (AM v NP), Perfect Matchings (RNC v NC).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34579123538644751112007-08-15T15:44:00.000-05:002007-08-15T15:44:00.000-05:00The key for me is your statement that most of the ...The key for me is your statement that most of the students will not be doing theory. <BR/><BR/>In that case, the course outline seems skewed heavily towards theoreticians. I'd break it down something like<BR/><BR/>* Why P-time (TMs, invariance of machine models, basic hierarchy theorems)<BR/><BR/>* Trust but verify: non-d time, non-d space. Savitch's theorem, Cook's theorem, Reductions<BR/><BR/>* Let's play a game: PSPACE, QBF, ptime-hierarchy in terms of alternating TMs ? <BR/><BR/>* Can someone please prove a lower bound ? Circuits, why non-uniformity is needed, lower bounds for circuits, relation to parallel computing<BR/><BR/>* Should I toss a coin ? randomness, BPP, RP, BPP and circuit classes; hardness vs randomness<BR/><BR/>* Let's talk ! Interaction, IP, PSPACE, PCPs, communication complexity. Link to approximation hardness. <BR/><BR/>* Wave/particle ? rudimentary quantum complexity: BQP vs NP. <BR/><BR/>Things deliberately omitted because the audience is not specialist theory: oracles, natural proofs, sparseness, details of MA/AM/MIP=NEXP, Toda's theoremSuresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51046154593411205932007-08-15T15:00:00.000-05:002007-08-15T15:00:00.000-05:00You'd rather prove Toda's theorem then IP = PSPACE...You'd rather prove Toda's theorem then IP = PSPACE?Anonymousnoreply@blogger.com