Open papers (by guest blogger Rahul Santhanam)

Lance has posted quite a lot on conference papers, review processes and the like recently, so one more won't hurt. Because of the resource constraints on program committees and the page limits on submissions, we have "standard" FOCS/STOC papers, which may contain two or three main results which improve in a natural way on previous results, proofs for the results which have a certain minimum technical complexity, and a few clever new ideas underlying the proofs. This is a good thing in that it steadily advances the state of the art in established areas, and in that it creates a congenial climate for collaboration because results are efficiently transmitted (one need only note the difference from previous results) and proofs easily digested (by understanding the role of the new ideas).

But my personal preference is for papers which are more mysterious, in which the results may be a little less clean. Research is often awkward (as opposed to the products of research, which are more often beautiful than not). I like papers which reflect this, in which perhaps there is some backtracking and re-examination of assumptions because a conventional line of research is stalled , or in which the motivation is not a technical but rather a philosophical question, or in which a promising idea is proposed which hasn't yet found an interesting application, or in which a connection between two disparate areas is hinted at but not completely formalized. By their very nature, their acknowledgement of contingency, these papers open themselves up to the reader; they are speculative, not authoritative, and by their speculativeness they inspire speculation in the reader. Also, since the results in open papers may not be compelling in themselves, the authors may be forced to make a stronger case for their ideas - this lays bare intuitions which in normal circumstances are shrouded within proofs.

My personal favorite among open papers, reflecting my interest in pseudorandomness, is Sipser's "Expanders, randomness or time versus space", which is all of 4 pages long. I was wondering whether the STOC/FOCS climate has become less receptive to openness of late, but in fact during my time as a graduate student there have been several instances that have caught my attention... Here is a (necessarily subjective) list: this one, this one, this one and this one. And it is a vindication of openness, of the primacy of ideas over short-term results, that the last-mentioned paper led, directly or indirectly, to this.