A Note on FOCS 2009 Two Page Descriptions

What is the purpose of the 2 page description, and how does it differ from a well written introduction in the 10 page abstract?

Let me try to answer this question by example. Here is the 10 page abstract for a paper that we submitted to STOC 09 [pdf]. The paper "The quantum detectability lemma and quantum gap amplification" is joint work with Dorit Aharonov, Itai Arad and Zeph Landau. I believe the introduction would be considered well written by typical STOC/FOCS standards - it tries to explain the context of the results, provides an informal statement, tries to informally sketch some of the key ideas that go into the proof, and last but not least, it brags about the significance of the results. The paper was accepted to STOC.

Here is a 2 page description we put together for this paper, just as an exercise [pdf,ps]. Let me point out a few features: 1) It incorporates a cleaner statement of the main result, that occurred to us while putting together the 2 page description. 2) The second page gives a self contained proof of the result in the special case of a very simple constraint graph on 2 layers. This special case illustrates many of the basic ideas of the general proof, involves minimal notation, and is much shorter and easier to read. It would make it much easier to referee the paper, since now the referee would start with a clear picture of the result and a broad outline of the proof. And it makes the result more broadly accessible beyond just a handful of experts.

The exercise of putting together a 2 page description provided the freedom to jump straight to the point without providing all the background or details, to be informal when desired, to require the appropriate level of expertise from the reader, and to leave the bragging for the 10 page abstract.