Sunday, June 05, 2005

A short SODA paper post

The SODA deadline continues to creep insidiously and subtly closer. As has been commented on before, this year there is no specific invitation for short (two page) papers as there has been in previous years, just a general suggestion to consider submitting papers that are considerably shorter than the ten page limit.

I have mixed feelings about this. From my perspective as an occasional SODA author, this is no great loss: I've tried to write a few short SODA papers in my time and had no great success with it. It's very hard to get things into this short a space. Mostly these efforts collapsed before being submitted, but in one case it got as far as being submitted but did not make it in. Eventually all these ideas were broadened out to full length papers and appeared elsewhere, given room to breathe instead of being crushed in to the short format. Although the material was significantly expanded, the fact that it eventually became a full paper meant that it was never really appropriate for the short form. Given the incredibly low acceptance rates for short papers, I resolved that I should never try to write a short SODA paper, so the fact that the suggestion to do so in the call for papers has been curtailed is no great loss.

But some of my favourite SODA papers, certainly some of the most memorable (less to forget?) have been short ones. I'm thinking of examples like Thorup's paper on universal hashing, Gupta and Zane's paper on Counting Inversions in Lists, and Kalai's paper on efficient pattern matching with don't cares all spring to mind, since they are crisply written and strong results on topics close to my heart. Zwick's paper on Jenga also deserves a mention, although it is short-ish, rather than short according to the standard SODA definition.

Lastly, I will miss the annual argument about short papers at the SODA business meeting. It was like meeting a favourite old friend in a bar, and hearing him repeat his old anecdotes over again: the same back and forth every year, the same attempt to force a vote but with a complete lack of conclusion, and all accompanied by a beer or soda provided to keep the audience docile. Maybe next year we will have the argument over again just for old times' sake.

So, goodbye short SODA papers. Although no category exists anymore, I hope that the same good material will continue to get submitted, and accepted to the conference. Most importantly, I hope that the authors of such papers don't try to artificially inflate their papers to 10 pages, but can express themselves concisely in three or four pages.

Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away. It's a nice sentinment Antoine, but couldn't you make it a bit snappier?


  1. "Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away. It's a nice sentinment Antoine, but couldn't you make it a bit snappier? "


    Posted by Thane Plambeck

  2. I think you forgot Swamy's SODA 04 paper... 

    Posted by Anonymous

  3. I can't resist mentioning one of my favorite short papers, which not only predates SODA short submissions, but SODA itself: "An old linear programming algorithm runs in polynomial time", by Boris Yamnitsky and Leonid A. Levin, in 23rd FOCS (1982), pp 327--328 (where page 328 has 5 lines of text, plus references).

    The algorithm works like the ellipsoid algorithm, but instead of using a containing ellipsoid, it uses a containing simplex.

    Posted by David Applegate


Disqus for The Geomblog