Complexity theory course wrapup

(Followup to my previous post. This is the last on this topic — I promise!)

Overall I was fairly pleased with how the complexity course I taught this past semester went. Still, there are are few things I would change, or at least that I would like to change, the next time I teach it.

What would I add?

At the beginning of the semester, I had planned to cover more material. There are of course several topics I could add, but what struck me the most looking back over the course was that, with one exception, I didn’t cover a single result from after 1995. Somehow that seems wrong, and I’d like to fix it. Any suggestions for what new(er) results to add? My personal constraints are: (1) it should be a topic that is (relatively) easy to motivate for students from outside TCS, and (2) it should be something where I can cover the full proof, or at least a full proof of the main components, in some “reasonable” number of lectures, conditioned on the other material I already cover. (I don’t like presenting “high-level overviews” of results, which is why I wouldn’t cover Williams’s recent ACC0 lower bound, for example.)

As far as my personal interests go, I would probably spend more time on time- and space-bounded derandomization (including Reingold’s result that SL=L), and possibly average-case complexity. Perhaps I could cover Dinur’s proof of the PCP theorem. I had also planned to cover the (old!) proof that TIME(t) is contained in SPACE(t/log t), and may finally get to that next time.

The only other (minor) thing I would add is a proof of oblivious TM simulation. I didn’t cover it this time around because I didn’t think the result was worth the tedious details of the proof. But oblivious simulation seems necessary (or at least highly beneficial) for several other results, and important enough in its own right, that I think I will add it next time.

What would I cut?

Unfortunately, for every topic added some other topic must be taken away. (This year, for example, I cut Mahaney’s theorem and didn’t feel any loss.) So what goes?

• For starters, I think some lectures can be compressed: my first three lectures, for example, (where I introduce Turing machines, P, NP, and NP-completeness) could surely be compressed to two, and I probably don’t need two lectures to prove IP=PSPACE.
• I may cut my half-lecture discussion on time-space tradeoffs for SAT. I like the result a lot (and will be sad to see it go), and the fact that there is a relatively simple proof is nice, but somehow I don’t find the proof very illuminating and it seems disconnected from other material.
• As discussed extensively here, I am going to pass on teaching Ladner’s theorem next time. (Though I will still mention the result.) I may cut the discussion of the BGS relativization of P vs. NP, though I consider that result important enough that I would think twice before doing so.
• I’d be ok with losing the lecture on zero knowledge. Cool as zero knowledge is, I consider it a “crypto” topic rather than a “complexity” topic.
• I taught Toda’s theorem for the first time this year, but think I will cut it next time around. For one thing, I was not able to convince myself (or the students) why the result is fundamentally interesting — on the face of it, the theorem just relates two complexity classes that are both much more powerful than P. The only argument I can see in its favor is that it shows the power of #P, but I think one’s intuition already says that #P is pretty powerful, and the proof of Toda’s theorem is way too messy to justify this benefit. (I realize that Toda’s theorem has historical significance, but I don’t think that justifies covering it now.)

Other suggestions?