Wednesday, September 12, 2007

SODA papers are out. Plus...

Request: If you want me to post a CALL FOR PAPERS or LIST OF ACCEPTED PAPERS or whatnot for a theory conference or some other conference, please email me and I will almost certainly do it. Not so good to make the request in a comment to another posting since some people do not read the comments (gee, I wonder why :-) ) For those who did not read the comments from yesterdays blog, SODA paper list is out and is here

This raises the questions of which conferences have the most complexity theory in them (say by percent). Here is my rough guess.
  2. MFCS
  3. ICALP
  5. LICS has an occasional article on descriptive complexity)
  6. SODA has an occasional lower bound. The few SODA papers I've been asked to subreferee have all ended up being rejected. The very fact that I am being asked to subreferee is an indicator that they are out of scope.
  7. COLT/ALT and the other Learning Theory Conferences.
If I left out your favorite conference, sorry about that.


  1. STACS often has complexity.

  2. Depending on how broad your definition of complexity is (does it include zero knowledge?), you can add Crypto.

  3. No quantum papers?

  4. Does anyone know when the reviews of SODA submissions are going to be mailed out? Thanks.

  5. To anon 4:
    Perhaps they are preparing the reviews. I have seen very strong papers rejected and some very weak ones being accepted in this SODA. Strangest SODA I have seen!

  6. Strangest SODA I have seen!

    I wonder how much of this is due to the composition of the PC. Starting from the chair down it has many members who do not regularly publish in SODA, including at least three committee members with no papers in SODA whatsoever, as per DBLP.

  7. All those "SODA quality" whiners have to realize that

    1) this is not the strangest SODA you've seen. Just because your paper did not make it, does not mean that many weak papers got in, and strong ones did not.

    2) SODA is a huge conference with a huge committee. We don't have that many important algorithmic results to fill in the program with high quality papers (best anyway go to STOC/FOCS). Thus, you always get about 10-15 nice papers surrounded by somewhat random "program fillers". Which program fillers make it indeed depends on the taste of the committee, but it does not really matter from the perspective of "advancement of science".

    3) The committee does not have time to really review the paper. This means that, occasionally, a FEW strong/weak papers make/don't make it. It's a shame, but not a tragedy. For the large part, however, the selected/non-selected papers are of the "average" quality, so you cannot make such generalizations regarding the quality of the program. The important thing is that the tails are generally where they should be, and the rest does not matter.

    4) I thought the committee was quite good and distinguished. It's healthy to occasionally bring a few outsiders to the committee.

    FYI, I'm not a SODA hater, quite the opposite (I enjoy attending the conference and have a few SODA papers). I just don't have illusions about the high statue of the conference as compared to STOC/FOCS, and even the leading CRYPTO conferences. I'm also trying to bring out some spice to the blog :).

  8. This raises the questions of which conferences have the most complexity theory in them (say by percent).

    This is the wrong version of the question to ask. Who cares about "complexity purity" like this? The interesting question for a complexity researcher should be "where can I find the most/best complexity research?"

  9. Anonymous 7 really missed the mark. For one there is only one post about quality here, and it is not quite a whine. Second, it is very questionable that the best algorithmic results get submitted to STOC/FOCS. From what I hear researchers submit "algorithmic" results to whichever one of STOC/FOCS/SODA (and SoCG if geometry oriented) has the closest deadline. Third, for the last few years SODA has had quite a bit of "outsiders" in its committee, certainly a lot more than STOC/FOCS. This year was an extreme, to the point that when the chair was announced many in the audience said "who?". To be sure, the chair is a very distinguished researcher, the "who" was a reflection of his not being a part of the SODA community, not of the lack of quality in his part.

    Lastly Anon 7 does seem to have plenty of illusions about the stature of the conference. SODA is nibbling at the toes of STOC/FOCS, and doing extremely well for a conference that takes in twice as many papers as STOC and FOCS. Just refer to the top ten lists posted in Suresh's blog for an apples to apples comparison of quality. Remember boys and girls, the best conference is not the one which accepts the least number of papers, but the one that accepts the right number of papers. In my opinion FOCS accepts far too few, STOC is closer to target but below the right number, SODA is about right or perhaps a tad over on the large side.

  10. I do not know what papers are rejected, but on the basis of what papers are accepted, it is a great list of papers. It is pleasure to see, some of the good papers which did not make to FOCS, are accepted to SODA.

    Overall I think it is a job well done by the SODA committee. (Again on the basis of partial information only i.e., list of accepted papers and not rejected papers).

  11. In Europe there's a nice conference with lots of complexity related papers in it: Computability in Europe