What should be in an automata course: Two views based on recent experience

(Joint Post with Subrahmanyam Kalyanasundaram)

In this post, I speculated on what I might put into my automata theory course. That prompted Subrahmanyam Kalyanasundaram, a PhD student at Georgia Tech, who was teaching Automata theory this spring, to begin a private correspondence with me. Now that both of our courses are over we can tell you what happened.

1. BILL: I did do Decidability of WS1S (weak second order with Successor and less-than). This was a real win-win-win. (1) It was a nice application of Automata Theory. (2) When I spoke about P and NP and they wanted a natural problem that is KNOWN to not be in NP, Dec of WS1S had already been discussed so I could refer to it and they thought it was natural (I would agree). (3) When I spoke about computability theory and they wanted a natural problem that was not computable I could talk about Hilbert's tenth problem. Since they already had the notion of a fragment of math being decidable or not. Will definitely do this again. Another pro - you can ask real questions about it.
   SUBRUK: I didn't do this.
2. BILL: Non-Graph-Isom is in AM. I had to do it informally and not prove anything about it. That's fine. I did not do enough of it to be able to ask questions about it. That is a problem with the material. It did give them a plausible intermediary problem (in NP, likely not in P, likely not NPC). Will do it again, it's short, but will think harder about asking them questions about it.
   SUBRUK: I thought about doing this but ended up doing Communication Complexity instead. But I might do this in the future. I only had a few lectures at the end for non traditional topics.
3. BILL and SUBRUK: Neither of us did Ladner's theorem or the time-hierarchy theorem.
   BILL's REASON: These yield unnatural sets and hence are not of that much interest. Or to put it another way: if a student says ''is there a problem that is decidable but not in NP'' they would much rather see WS1S than a construction of an artificial set. And I agree with them.
4. BILL and SUBRUK: Neither of us did primitive recursive. There is no real punch-line there. And we won't in the future.
5. BILL: I didn't do proofs of obvious things. And I won't in the future. I did constructions (e.g., Reg Exp == DFA == NDFA) but did not prove that they work since they obviously work.
   SUBRUK: I did some stuff with TM equivalence that is kind-of obvious which I will skip next time I do the course. Similarly, I may follow BILL's approach on things like Reg Exp == DFA == NDFA in the future.
6. BILL: Didn't do ZK protocol for SAT. That I would have liked to do and may do in the future; however, we lost two days to snow so that made the semester more time compressed. This I think I COULD make up questions on.
7. BILL and SUBRUK: We didn't do Mahaney's theorem (if there is a sparse NPC set then P=NP). The PRO of this would have been that there are LOTS I could ask about it. The CON is that there is no punchline for them. I don't really want to go into the Berman-Hartmanis conjecture. BILL personally likes this material (see here) but that is not a good reason to tell them about it. SUBRUK didn't want to start anything that heavy in the few days he had for non-traditional topics.
8. BILL and SUBRUK: Neither of us did Det PDA's.
9. BILL and SUBRUK: Both of us did the poly time algorithm for CFGs. This is nice since it fits CFGs in between REG and P.
10. SUBRUK did a little bit of Communication Complexity Lower Bounds. It was nice and he says that the students liked it. It did not even occur to BILL to do this, but he may consider it in the future.
11. SUBRUK pondered doing the poly hierarchy but didn't. When he was talking about Sigma-2-P he found that it was hard to keep students interested, and so decided to not cover PH. BILL speculates that this may be true since there are no natural problems there.
12. SUBRUK did space complexity, NL-completeness, NL = co-NL, Savitch's theorem, PSPACE-completeness. BILL didn't do any of this but is intrigued by the notion of doing it and may consider it in the future.
13. BILL's Future: SUBRUK has given me some things to think about doing which I had not thought of before. I may move some in or out in the future. If I teach this course many years in a row I will need to vary it some for my own sanity. (Some would say it's too late to worry about that.)
14. SUBRUK's Future: As noted above, less details on things that are obvious. I would use the extra time to do more interesting non-traditional topics like Interactive Proofs or Zero Knowledge. I might keep varying some of the topics, to see if some new topics might be worth adding.