Posted by: jonkatz | December 14, 2011

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?



  1. Actually, you did have materials after 1995 and it is one of the parts you are thinking about dropping: Time-space tradeoffs for SAT: Lance’s first tradeoff result is from 1997 with the improvements coming 1999 onwards.

  2. My opinions
    1) Do not add obvlious TM simulations.
    2) As for Toda’s result- certainly do Valiant-Vazarani and mention Toda
    and that is uses some of the same ideas.
    3) When I taught the course (the SAME course- I am at UMCP!) I had
    the students meet in small groups outside of class and discuss some theorems
    and present them to me for half of the HW.s For example, They leaned
    NL=coNL this way.
    4) Unique Game Conjecture might be worth covering- the statement and
    what you can prove from it.
    5) I wouldn’t be bent out of shape about all the results being pre 1995.
    In a typical first year math grad course the results are pre 1885.

  3. +1 on GASARCH’s final point. Well said, sir!

    Amit C

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: