Teaching

Through an unexpected turn of events, I am teaching CS 172 at Berkeley. This is the standard course on Finite Automata, Regular Grammars, Turing Machines, undecidability, NP-completeness, etc. At Berkeley it is a course aimed primarily for seniors (i.e. it comes after Algorithms, Discrete Math, and usually other "advanced" courses).

Bill Steiger taught the first weeks (finite automata), but unfortunately he has had to return to New Jersey unexpectedly, and I was asked to take over.

So why did I accept? On the one hand, I can cite Feynman on why teaching is important: if you research fails for a while, you can at least find comfort in your constant teaching. But since said comfort is so easily found in wine, this does not quite explain it.

The main reason I accepted was that I remember taking this course with Mike Sipser in sophomore year: it was all so much fun. No student needs to go through this! This course should be significantly redesigned, and by teaching it, I can take a stab at the new version.

The main reasons I dislike the course are: (1) the mental masturbation: teach kids clean unimportant topics (because they're clean and elegant); and (2) the very out-dated perspective, which might have seemed elegant at the time, but with time has proven misleading. Here are some examples:

• the pumping lemma. In the era in which limited state matters (think streaming algorithms), and we have many exciting developments in understanding limited state (by lower bounds), we have students memorize a mechanical way to show that {w w^R} is not regular.
  
  
• push-down automata. In case you don't remember this: push-down automata are not a nice limited class of machines that can parse grammars --- they are nondeterministic ! Grammars that need the whole nondeterministic shebang are parsed via dynamic programs (most famously, the Earley). More restricted classes are parsed by algorithms with cryptic names, like the LALR parser.
  
  
• the lack of exciting stuff in the undecidability section. People in programming languages and databases go on and on about decidable and undecidable logics. Surely there has to be a more exciting example than the Post correspondence problem (and, no, all rights to use "PCP" for this problem have been revoked as of 1990).
  
  
• Turing machines. All computer-looking models of computation are equivalent within logarithmic (often constant) factors. Saying that we cannot fix a model of computation with less than a polynomial imprecision in the running times can only lead to a new generation of seriously misguided theorists.
  
  
• the P vs NP fetish. I have too much to say about this, so let's keep it for another post. Suffice it to say that the P vs NP fetish has led to people ignoring major topics like fixed-parameter tractability or SAT sparsification.
  
  
• a dry approach to space complexity. While things like NL= coNL are reasonably interesting, they seem to me far less interesting than space/time trade-offs. The issue of space/time trade-offs (which has some connection to what computation means in the real world) is completely buried by looking only at the space complexity alone, leading to some unexciting language theory.
  

My attempts to "fix" the course will be documented on this blog. In the time, please suggest your favorite topic that you think should be covered in introductory complexity courses.

FOCS 2009

Sorry for not blogging. It's not that I've been busy -- it's more like incredibly busy.

Anyway, the FOCS 2009 call for papers seems to be out. Following are the key changes in the call.

Pre-submission abstracts: are out. As I said before, I am against them.


Full proofs: are required for the "central claims in the paper." Essentially, you don't need to prove that 3rd extension of your results that nobody will care about, but you need to write a complete proof of the main result (i.e. the really interesting result for which the paper is being accepted). When SODA'09 introduced this, my gut feeling was slightly against, but with time as a good advisor, I have become a convert. I am glad I managed to push this into the call (it was harder than I had expected...)

Here are excerpts from mails that I wrote on this topic:

[...] It happens too often that people submit a paper vague enough that an interested reviewer cannot even refute (how can you give counter-examples to something that is not fully specified in the paper?). Obviously, the job of conferences is not to check correctness, but if we get lucky with a passionate reviewer, we should allow him to do the job right.

[...] PCmember makes a valid point that the committee can (and should) ask for clarifications when a proof is missing or unclear. But this does not rule out the following scenario:

" Lemmas 13 to 15 don't have proofs in the paper. The reviewers never themselves thought about the problem, and the lemmas appear quite reasonable and straight-forward, so no objection is raised (no need to bother the author for a technicality). After the paper is published, somebody who has thought about the problem reads the proof and has doubts about Lemma 14. What now? "

The paper should be verifiable not only by the committee (whose emails the author will certainly not ignore!) but also by future readers (imagine the authors' response time if the future reader is a guy with a funny name from China :).

I hope asking for complete proofs becomes standard. As with journals, the main reason to trust the proof is not that somebody else formally checked it, but that the author carefully wrote down a detailed proof.


Post-submission description: This is the biggest innovation in the call. You are supposed to write a 2-page description of your paper one week after the deadline, in which you informally describe the contribution, the main ideas etc.

I am very sorry that this made it. To be blunt, I think the two main reasons this idea made it were:

1. Some people thought something is "wrong" with current STOC/FOCS and something should be changed. People didn't quite have a consistent story of what was wrong or what should be changed, but the desire of change made the PC agree with the most radical experiment on the table.
   
   
2. There was no vote (almost nobody responded to a request for a vote). I have no idea whether 75% of the PC supports this, or a vocal 20% of the PC supported it. An unfortunate state of fact.
   

My formal objection was the following (several people agreed in private emails):

Essentially, we can make the conference system as complicated as we want: pre-submission abstracts, double blind, 2-page summary, video at time of submission, rebuttals, a million rules for conflicts of interest etc etc. Some field which obsess about some central conference implement some subset of these ideas (think SIGGRAPH, SIGCOMM etc). Fortunately, in theory we have avoided all this non-sense.

We are implementing the basic systems principle: keep the interface simple. The process is minimal (submit a paper, get a decision and reviews). Since we have a fast turn-around cycle (with two major conferences a year, plus other reasonable conferences like SODA), there is no need to "bullet-proof" one conference. Any mistake by a PC should be rectified by the next one if the author clears up the misunderstandings in his paper.

What would the 2-page abstract do? It would force me to cut some arbitrary part of my introduction (I typically have around 4 pages). Why impose this 2 page fixed format for what should be the introduction?

Also, the 2-page abstracts would sanction the idea that a foggy introduction written at the last minute is ok, since you can rectify it 1 week later. -- Yes, yes, we threated that we may not read the 2-page abstract, but that is also wrong. If we actually don't read it, we seem like the evil PC that just wants to keep authors busy for no good reason. And any argument that "thinking about your contribution 1 week later is good for you" is as annoying as any paternalistic argument.

Theory has a light-weight process centered on ideas. Anything else should be minimized. Let's keep it simple.

To be clear, everybody seemed to agree that the 2-page description is only an experiment, and future PCs should not borrow it without serious review. I hope it will die after this conference.

Against Pre-Submission Abstracts

Claire Mathieu's SODA and Michael Mitzenmacher's STOC asked for paper abstracts to be submitted one week in advance of the deadline. As the FOCS'09 PC is debating this issue, I wrote the following email expressing my objections. I hope this makes sense to enough people, and we will abandon pre-submission abstracts in theory conferences.

I am strongly opposed to the 1-paragraph pre-submission abstracts, so let me try to argue against them.

Many people, myself included, only write papers in the last week before the deadline. It doesn't matter why this happens, but the PC has to be accommodating. We cannot lecture the community about how they "should" write papers.

( If the argument about being accommodating is not a strong enough for you, I claim that it is, in fact, the optimal rational decision to only write papers the week before. If you're working on several problems at the same time, you're usually stuck waiting for some brilliant idea to move forward. Such ideas come more frequently when you're relaxed and allow your mind to explore improbable paths --- i.e., such ideas tend not to come in the last week. Writing a formal paper, however, is a much more predictable thing: apply brain power, get the proof. This can be done in the last week, even when sleeping little and working with a time constraint. )

If we accept the fact that some authors will write papers in the last week, it means that many of the abstracts will not materialize into papers (if a bug is found, or if the writing is not finished in time --- especially likely if complete proofs are required by submission).

Abstracts that do not materialize into papers are annoying for everybody. For the authors, they are annoying because you have to write an abstract for something that doesn't exist yet, describing some results that might change slightly, and you're not even sure that all proofs will work and you will actually submit!

For the committee, they're annoying because you are reading and bidding on non-existent papers, generating useless work.

I don't see why these disadvantages are worth it. After all, we're only saving a few days (eliminating paper proceedings would probably save a month!).

Cheers,
-mip