STOC 2008 is coming up in a few days. Though I think it is important to attend STOC/FOCS even when you don't have a paper, I was simply too disappointed by this conference to go.
Scrolling down the list of 83 accepted papers, I could not help marvel at the almost-complete lack of (non-approximation) algorithms from the program. Alas, this was not really for lack of submissions. I know of several papers that were submitted, and in my opinion, should have been very easy STOC/FOCS accepts. (Since these are not my own papers and not yet published, I cannot really talk about them.)
Quite likely, the heavy bias against algorithms was due in part to the composition of the PC, which essentially contained nobody in the area. But another way to view it is that algorithms were collateral damage in the raging war on whether it is conceptually more important to approximate the Stochastic Traveling Dog and Pony Problem with Piecewise Linear Costs, or the Games that People Don't PlayTM. (IMHO, the best papers from these fields always got in; it is only the marginal papers that need a boost for being "conceptual"... But that is a topic for another discussion.)
Based on the rantings that you can hear left and right (and, during this spring's interviews, STOC'08 was a popular topic of conversation), it seems the war might have taken its toll on the quality of the conference as a whole. Reportedly, this STOC contains about 10 papers rejected from SODA'08 and 15 papers rejected from FOCS'07.
If these numbers are true, there is serious reason to worry about what this conceptual drive is doing to our academic standards (no, we don't really believe that all these papers were improved substantially from the past submission...) To quote a PC member from a past conference: "These papers were not rejected for being too conceptual, they were rejected for being too weak."
If you were on the SODA or FOCS PC and would like to confirm these numbers or post your own count, please leave an anonymous comment or send me personal email. The latter is preferable because it makes the message trustworthy. I will post your recount, but your identity will remain forever secret.
Quoth Mihai: ... heavy bias against algorithms was due in part to the composition of the PC, which essentially contained nobody in the area.
ReplyDeleteBernard Chazelle, inventor of linear-time triangulation and inverse-Ackermann-time MST, and co-inventor of fractional cascading, not algorithms-y enough for you?
Not that Bernard was the only algorithms-ist (ugh) on the PC, but I've got to defend my advisor...
- Amit C
Yes, I'm vaguely aware of Bernard Chazelle's work. A quick grep through my papers directory seems to reveal 63 citations ;)
ReplyDeleteit's funny how he ignored Amit's point and gave a stat about himself again. haha.
ReplyDeleteI don't think there was any serious point from Amit...
ReplyDeleteI have no comment on the algorithms papers, but I found the quality of the complexity-ish and crypto-ish papers to be high this year. At least there were many that were interesting to me.
ReplyDeleteMihai, would you care to point out some papers in the STOC 08 program that you think are subpar?
ReplyDeleteAnon, there is a good reason why PCs should containt people from many areas. Even if I may understand what some paper in, say, crypto is talking about, I am not really able to judge its quality in context. So if you want me to jump at the neck of some papers, first convince the PC to accept some in algorithms :)
ReplyDeleteI am pointing to the reported number of STOC'08 papers that were previous rejects as an objective statistic that can be compared across subfields. That's why I would like this number verified.
Well, since I had FOCS paper that got invited to the special issue that was rejected from the previous STOC, I dont accept the observation that "reject from previous conference" is an indication of low quality. I am sure that many of these previous rejected papers are probably very good. Selection by PCs is a random process that does reject sometimes excellent papers. The assumption that a PC is a source wisdom when coming to judging quality of papers (especially when its on linear ponies) is natural, but somewhat optimistic.
ReplyDeleteAll PCs make many mistakes, thats what makes their decisions interesting.
What you learn quickly in an academic environment is that everybody has good arguments, and there are always counterexamples. Still, my own feeling is that STOC'08 went down a path that we should not continue on. If indeed the large count of decisions they "overturned" is correct, that is in my opinion reason to worry.
ReplyDeleteMihai, I cant comment on the algo papers that were rejected.
ReplyDeleteBut claim that there are good algo papers rejected from this conference..
Yet at the same time, you argue that the papers rejected from previous conferences are not as good.. These were probably the papers that were rejected last time because the PC didnt contain people from their corresponding fields..
I guess theory is so large now, that every conference some area gets hit badly..
I think 5-10 papers rejected to the previous STOC/FOCS conference that get accepted to the next installment is more or less standard. Sometime just rewriting the intro after being rejected is enough to dramatically improve its FOCS/STOC chances. As such, since the two PCs dont necessarily see exactly the same submission, its not even clear that one can claim that the first committee made a mistake.
ReplyDeleteAnyway, the important thing is to do good research. Whether the results appear in SWAT or FOCS is really of lesser importance.
Yes, the really important thing is to do good research. But it is also of major importance to point out good research for the next generation, because we will not solve all problems now.
ReplyDeleteThe reason I am spending so much time on this stupid politics is that I am genuinly worried by my impression that the current "sanctioned trend-chasing" is destroying our position to solve the really big problems.
Anon -2, I can certainly see your logical objection. Indeed, I hope that the FOCS PC will accept the good papers rejected from STOC.
ReplyDeleteBut you will agree with me that it's a laudable goal to be less arbitrary in our decisions. As such, it seems valid to criticize the perceived fact that a PC is making too abrupt departures from the established norm.
The right experiment to do would be to set up two PCs for the same conference, working on exactly the same set of papers, and check if the correlation between the decisions of the two PCs makes sense. (I would not expect 100% correlation; if the correlation is 20%, then we should be worried).
ReplyDeleteIf you want to save some work, and if you believe that the problem is in the PC itself and not in the reviewers, then you can give both PCs the same set of referee reports.
Mihai,
ReplyDeletethe main problem with your post is that most arguments are based on rumors (*Reportedly* 10 SODA rejects got into STOC; *I know of* some good algorithms papers that were rejected). No real statistic is given; just rumors. If you want to make an argument, you have to give some evidence of the real statistics, and compare it to other conferences. I bet, every year a certain number of SODA rejects make it into STOC. (And I bet some of the papers were improved before they were resubmitted!)
On the other hand, probably less SODA rejects make it into FOCS, and that's simply because the FOCS deadline is in early spring and the SODA deadline is in early summer.
All in all, your argument is not very convincing.
The current system works. It would be hard to argue that good research is not being done because of its imperfections. The only thing the current system discourages is a chase after the moon research (i.e., working on extremely hard problems directly, which has low probablity of success). This is of course a good property of the system, I would argue.
ReplyDeleteIn any case, ask yourself the following: "Do people work on the problems they really care about?" The answer is mostly yes, I think.
Or are you trying to argue that "conceptual" research would lead new students to do weak research instead of decent research? Maybe. But I think very quickly the bar for "conceptual" papers is going to be high enough that being conceptual, whatever that means, would be of very little advantage...
To quote a PC member from a past conference: "These papers were not rejected for being too conceptual, they were rejected for being too weak."
ReplyDeleteWhat else would you expect him/her to say? "The conceptual papers were great, but we don't do great conceptual papers"? The PC member might well be right, but either way the comment would have been the same.
The real question is if there are great conceptual papers out there getting rejected.
Clearly some of us do think this is the case. The reason is simple: referees use their standard issue "technical prowess" yardstick to measure conceptual papers and lo and behold, using that standard they are "too weak".