Friday, August 07, 2009

What To Do With the Little Theorems?

Last week Shahar Dobzinski asked the following question on Noam's blog:
Suppose you have an interesting result that has an easy, almost trivial proof. What is the best way to publish it? Writing a full, formal paper takes too much energy. Besides, a travel to a conference just to give a 5 minutes presentation is an overkill, and journals are just too slow (who reads them anyways?)
Let me understand: You only travel to conferences to give presentations, journals are worthless and you are just too lazy in any case to write up results with short proofs. Luckily Noam managed to talk Shahar into writing up the result for Arxiv. Here's my advice.

Suppose you have proven a new result. It is a good result but not earth shattering. The proof has a cute trick but not particularly deep. However this result will not on its own get accepted into a conference you want to attend. What do you with it?

First write it up. Make sure your proof is correct and your exposition clear. Show it to a a few friends. Then try to see if there is an interesting new extension or ways your new proof technique could be applied to other questions. Don't extend for extensions sake. Nothing worse than taking a cute little result and turning it into an ugly messy but still little result.

So you've decided that the little result stands alone. Next claim the result for yourself. Send your paper to one of the on-line archives. This will also let others see your result.

But you still need to publish your result? What to do next. It depends.

Sometimes I sneak little results into other papers I am working on. In the back with only a brief mention in the introduction. If the paper gets into a conference so does my little result. But I usually feel a bit guilty about this.

Some people take small results, dress them up as far more important than they really are, make the proof needlessly detailed and submit these papers, sometimes successfully, to major conferences. Congratulations you got another FOCS paper. But do you feel good about yourself?

Not every theorem has to show up in a conference. If only theoretical computer science had a journal for little results. We do, it is called Information Processing Letters which limits submissions to nine pages. Many of you are wary of submitting papers to an Elsevier journal like IPL, but many other journals accept short papers. Theory of Computing has a short communications section for example.

But at the very least don't leave a little result unwritten. Some little results turn out to be incredibly important parts of other work but only if people know about it. And someday someone will reprove your result and claim credit for it if you never did.

9 comments:

  1. I don't see what is the major issue here is. There are short papers; there are long papers; and there are very long papers. Most journals accept papers of all types, including short papers.

    Probably, the issue here (again) is that TCS people tend to think of research in FOCS-STOC units. To this one can only say -- grow up.

    ReplyDelete
  2. "Many of you are wary of submitting papers to an Elsevier journal like IPL", what's wrong with IPL???

    ReplyDelete
  3. that's how the spam websites work. they market each other. there is a mutual blog post marketing going on between lance and noam blog.

    ReplyDelete
  4. I know that Scott's blogged his "trivial results" in the past, and for theorists with well-read blogs, this is possibly even better than putting it on the arXiv. (Optimally, I guess you could do both...)

    It's also useful to write up little theorems just because it's a good idea to stay in the habit of writing stuff up, and it's easier (and more fun!) to experiment with your style, practice expository writing, etc., for little notes than it is for big, 40-page FOCS results.

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. > "Many of you are wary of submitting papers to
    > an Elsevier journal like IPL", what's wrong
    > with IPL???

    Have a look at, for example, this old posting by Lance and its comments.

    Ah, good times, good times.

    ReplyDelete
  7. There is no good reason to submit it to a journal first. If people might care, put it on the arxiv so it will be easily discovered. If it turns out that people do care, then later you can submit it to a journal. If not, no harm done.

    ReplyDelete
  8. From Lance's post: "But at the very least don't leave a little result unwritten. Some little results turn out to be incredibly important parts of other work but only if people know about it."

    I agree completely! Think about Erdos' idea about THE BOOK. Long and ugly proofs have no place there. TCS people have also a lot of such "the book" proofs. See e.g. one about the matrix rigidity. And especially in TCS -- this "alive" field, not yet trying to put their achievements into "big Bourbaki-type theories" -- publishing of short notes with cute ideas, is very important. Would a 1 page proof of Erdos-Rado "Sunflower Lemma" be accepted to FOCS/STOC? I think -- not.

    Unfortunately, we have so few places where to let such (small, but cute) ideas to land. Only IPL and some "short notes" sections in "serious" journals.

    Why not to open something like "The Book proofs in TCS?"

    ReplyDelete
  9. Electronic Journal of Combinatorics accepts notes which don't need to have as much introduction as a full research paper. It seems to be widely read, perhaps because it is open access. If the little theorem is a little theorem in combinatorics, I'd say send it to EJC as a note.

    ReplyDelete