Browse Groups

• ## [Computational Complexity] What To Do With the Little Theorems?

(1)
• NextPrevious
• 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
Message 1 of 1 , Aug 7, 2009
View Source
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.

--
Posted By Lance to Computational Complexity at 8/07/2009 05:42:00 AM
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.