Wednesday, September 07, 2005

Michael finds the elephant

..in the room:
I think STOC/FOCS has become progressively less algorithms-oriented over the years. My impression is that STOC/FOCS emphasizes "mathematical depth", "cleverness", and "theory purity" over, say, "usability" and "insight into a practical problem". I know there are a large number of people who think this, and I would therefore encourage people who don't see this or think it is true to simply consider the issue again. I do not wish to make a judgement call as to whether this is good or bad -- this is just what these conferences, I believe, have turned into.

SODA, not coincidentally, has become a refuge for more algorithmically oriented papers. (As have more specialized conferences.) In some ways, this is good -- these papers have a home! In some ways, it is bad, because I think it has exacerbated the division, which in part explains the extreme opinions the post has raised. (I too have had reviews essentially saying, "This is algorithmic, belongs in SODA." Perhaps the reviewer was just being kind and didn't want to negatively comment on the quality of my work. But my impression is that for many FOCS/STOC reviewers "algorithmic" has itself become a quality comment, in the sense that "algorithmic" papers that do not pass the "deep/clever/pure" test are pretty much dismissed out of hand.)

I have been on committees for FOCS/STOC conferences, and I feel that I have seen these biases in action. Strangely, I did not come away with any ideas on how to change things; once a culture develops, it seems very hard to change.
I'd like to point out that there is nothing inherently wrong with FOCS and STOC being exactly the way Michael describes them, as long as these biases are made clear. A conference is defined by its community, and by the papers it accepts. If I know that only "deep/clever/pure" papers should be sent to STOC/FOCS, it makes my life much easier, as long we are willing to relax the idea that only STOC/FOCS must represent the best that theory has to offer.

4 comments:

  1. My feeling is that, FOCS/STOC try to present ideas that have the potential to "stir up" the community (like a paper that introduces a new technique, or introduces an interesting new problem, or resolves a long-standing open problem). An ordinary "algorithmic" paper usually doesn't have that potential. Having said that, I think a good percentage of FOCS/STOC papers served that purpose resonablly well.
     

    Posted by Anonymous

    ReplyDelete
  2. I agree with Suresh's point; I was (in my post on Lance's blog) trying to avoid any judgement, assuming my description is correct. Perhaps it's all fine and good that things are that way. I just wanted to state my impression. 

    Posted by Michael Mitzenmacher

    ReplyDelete
  3. "as long we are willing to relax the idea that only STOC/FOCS must represent the best that theory has to offer. "

    I would be surprised if a breakthrough  paper in algorithms was not accept to STOC/FOCS. The issue seems more that a good but not amazing paper has its chance hurt if it is algorithmic. But if a paper has a strong practical slant, it's not clear why it should be heralded as tiptop theory work unless it really does something innovative anyway. Perhaps it's just that more practically minded researchers are very sensitive about being looked down on.

    There's also a huge ammount of algorithms research out there, and it's nice to see a wider cross section sometimea. 

    Posted by Anonymous

    ReplyDelete
  4. If the techniques of theory can be brought to bear on an important practical problem, such as linear programming, or primality testing, that is a tiptop theory paper, even if the main techniques were already known and the contribution lies only in combining them in the right form.

     

    Posted by Anonymous

    ReplyDelete

Disqus for The Geomblog