Tuesday, August 7, 2007


An anonymous commenter on the Complexity Blog recently complained that on the SODA'08 PC, there's nobody whom you'd really describe as a data-structures person. That seems to be roughly correct. I can add my own experience to support the claim: I got an unprecedented number of review requests, namely 6. Most of these had nothing to do with my research, and just had the keyword "data structures" somewhere in the intro, which seems to indicate a lack of expertise in the area among PC members.

In line with the current trend of doing objective statistics on our conferences (namely citation counts), it will be interesting to watch the list of accepted papers. The presence of data-structure papers at SODA is usually large, and I have heard the phrase "SODA is the data structures conference" quite a few times. I do not know whether the lack of PC members in the area increases or decreases the number of accepted papers, but this is our opportunity to find out. Even if the numbers come out right, the quality of the papers may be more mixed, since presumably an inexperienced PC makes more random decisions. That would be harder to assess.

[[Obligatory note: I hold no direct interest in this discussion, having only submitted one streaming paper.]]


Suresh Venkatasubramanian said...

To reiterate the point made after you made a similar complaint about the FOCS accepted list, you'd have to know more about the pool of DS papers submitted before you could make any inference based on the outcome.

The fact that the 6 papers sent to you had only tangential connection to your research (l'etat c'est moi ?) might also indicate something about the paucity of DS submissions in general

Anonymous said...

Actually, inexperienced reviewers seem make more tough decisions.

Mihai said...

Actually, inexperienced reviewers seem make more tough decisions.

Precisely. A review that comes back restating the introduction and saying that the paper seems correct is virtually useless.

Mihai said...

Suresh, the phenomenon I'm seeing is the following. I am a PC member and of course I get assigned some papers that are not in my area. I don't know enough about the paper to know who the best reviewer is, but wait --- the paper is about data structures and there's this funny guy I know from beer / flaming / gossip / whereever, that keeps talking about data structures...

Nothing in this chain of events can be blamed on anyone in particular... I'm quite convinced that 99%+ of the people out there are doing their PC jobs in all earnest.

The unfortunate thing is that a suboptimal review gives you incomplete information. What does that lead to? So people think it leads to fewer accepted papers in the area. But the more likely outcome, I believe, is that papers with bombastic introductions tend to get accepted. Some are good, some are bad -- and if you don't know the area too well, you'll think twice before claiming a paper with a convincing intro is actually weak.

On first count, last SODA had about 16 data-structure papers. Like I said, I would forecast a similar number this year, despite the PC composition.

Anonymous said...

Ok, so a conservative estimate is 1/8 of the papers are on data structures. On a committee of this size (4 people more than last year) there should be AT LEAST one person versed in data structures. (I can't imagine the same sorry situation happening to game theory, or approximation algorithms, or geometry, etc... all areas well represented at SODA in recent years.) I think Mihai should question Teng at the business meeting on how he composed this committee. Maybe he'll say something candid like "my bad" or "I didn't realize data structures was a field" or "who ISN'T qualified to evaluate a data structures paper?"

Anonymous said...

It seems to me that data structures, though a fundamental area, has not been "hot" for many years. Perhaps, this is an indication as to the composition of this committee.

It seems to me that Teng did not do a very good job in selecting the committee members...too many people working in game theory..

Anonymous said...

Data structures may or may not be hot, but there are typically quite a few submissions in related areas like streaming. There is no PC member on streaming either!

Instead we have lots of people on random graphs and games. Pretty bad composition.