There are several other interesting looking papers, including Zuckerman's Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number, Ambainis, Spalek and de Wolf on Quantum Direct Product Theorems and Charikar, Makarychev and Makarychev with Near-Optimal Algorithms for Unique Games. I can't find the latter online but here is the result from a talk abstract.
We present new approximation algorithms for unique games that satisfy roughly k-ε/2 and 1 - O((ε log k)1/2) fraction of all constraints if 1 - ε fraction of all constraints is satisfiable. These results show limitations on the hardness bounds achievable using UGC. In particular, they disprove a stronger version of UGC that was conjectured in a recent paper. Somewhat surprisingly, even a slight improvement of our results (beyond low order terms) will disprove the unique games conjecture.Many more interesting papers, be sure to look the list over yourself.
This is grumbling from someone whose paper got rejected from STOC, so can safely be ignored.
ReplyDeleteStill: why is the feedback from the committee so awful, and why does it take so long to get comments from the committee (this is not just a problem this year, but has been an issue in previous years as well)?
Also, why do I continually get the sense that 60-70% of a STOC acceptance is based on what might politely be called a "popularity contest"? That's not to say that there weren't some great papers (by well-known people) that got accepted. Just that I see plenty of weaker results with well-known authors, too.
I agree with the previous comment. The feedback from STOC/FOCS committees on submissions (both accepted and rejected) is almost always awful; essentially a binary value. Some of the "lesser" theory conferneces do a wondeful job of giving valuable feedback from one or two reviewers. Having served on STOC/FOCS committees, I know that a lot of work does go into evaluating the submissions. It would be tremendous help if the committee could take time to convey that information (objectively) to the authors. For such high stakes conferences as STOC/FOCS, it is important to maintain credibility of objective review process. Otherwise feelings like those expressed in the previous comment will become more prevalent and could get worse.
ReplyDelete-rant-
ReplyDeleteAlong the same lines, I was immensely disappointed by Cliff Stein's comments at the SODA business meeting. "We should decrease authors' expectations for feedback." So if you only expect a decision, but then get some feedback, you'll feel great.
Maybe one of the senior members can chime in and tell us why in fields outside of TCS a rejection is often followed by several paragraphs of constructive & insightful comments from each of the reviewers, whereas in TCS you should be happy if you get a single review back that says something other than "there's a comma missing on p.9."
Surely this is not because the theory PC members don't have time to write comments (as that would be the lamest excuse in the book). If you want, you can blame it on the review system, but why not switch to a different system then? (The whole "email your correctly named file to this address after registering" is so 1995 anyway - we can upload from browsers nowadays, really!).
Review comments advance the field, by providing relevant feedback to the authors. Without them, we'll just resubmit the paper exactly the same until it finally gets in somewhere.
Personally, I find the lack of comments in theory conferences simply unacceptable. But hey, I'm just a lowly graduate student.
-end rant-
"Why does it take so long to get comments from the committee"
ReplyDelete1. The notification date in the CFP was announced as Jan. 31. That's today, isn't it?
2. The software that handles on-line comments from PC members requires that reviews be explicitly tagged as being able to be released to authors in order for this to happen since confidential information can easily creep into the on-line reviews (e.g. explicit references to sub-referees and other papers that are submitted to the conference). Since the on-line discussion goes on right until the PC meeting, PC members need some time to go through the ~40 papers each of them has to review before the reviews can be sent out.
There are also sometimes issues with merged papers that can require a week or so to handle so having the notification date be immediately after the PC meeting is not ideal.
3. A PC chair can only cajole so much in terms of getting PC members to convert their reviews into a form that can go back to authors. Part of the problem is that being on a PC is so much work (and the determining the program typically takes every hour scheduled for the meeting) that some PC members decompress immediately afterward and do not end up converting their reviews in time for author notifications.
Paul Beame
Paul Beame's comments above may be a valid explanation but not a valid excuse. They just mean (i) may be the PC meetings and notification deadlines should be well-separated, (ii) may be the on-line review system is lousy, (iii) may be the PC chairs and members are not doing their jobs right -- they might be feeling that they are already doing so much "service" to the community by sitting on a PC that it is unfair to expect them to justify their decisions. All of these are fixable.
ReplyDeleteI think that an excellent way to force committee members to write good reviews for papers is to open up reviews for author rebuttal, as several conferences in programming languages and computer architecture do.
ReplyDeleteRebuttal of reviews, while primarily meant to ensure that the reviews are all factually correct, force program committee members to be conscientious and write good reviews.
Sometimes I also had the weird experience of having a paper rejected while getting only good feedback (probably got struck down by a referee that didn't write author comments at all), and sometimes getting papers accepted with derogatory reviews. However a rebuttal system is a slippery slope towards the essence of endlessness.
ReplyDeleteMy humble suggestion - make the reviewers fill an online form (I second the "so 1995" remark), and in it mark fields by audience (e.g. "PC only"), function (e.g. "recommended action" and "detailed review") and maximal length. Now all you have to do is to limit all PC-only fields to not too many characters :-)
From someone who didn't get their paper rejected, I have two observations. First, the best 20-30 papers in this STOC look especially strong. And secondly, yes, the bottom papers, many of which I'm familiar with, appear to have participated in a popularity contest. I guess when deciding between the weaker papers, the committee figured that more famous people should get the benefit of the doubt.
ReplyDeleteEldar, your suggested system is practically in existence, and has been for some time. (But not to your exact specification.)
ReplyDeleteFor one, PODS has been using a system similar to that for several years. Specifically, Microsoft's conference management toolkit:
http://msrcmt.research.microsoft.com/cmt/
(Hmm. The above link claims that STOC has used their system in the past. Wonder what happened?)
Of course, even with an automated system like this, the PC members may still wish to filter a scathing sub-ref's "comments to the author" field... leading to another way in which some commentary might as well be withheld entirely.
sa adsm pointed out at the SODA business meeting, it would not be hard to have all comments go to authors by default, rather than the default being NOT, as it is now.
ReplyDeletei will say this though: i second the complaints about the submission system, but this is not the real problem. no system can force people to update reviews. I think in general going towards gearing things so that comments are public by default is a good start though.
For those who complain about the submission software: it was written by TCS folks. If you don't like it, write your own and contact the SIGACT folks: they'd be happy to "modernize" things.
One of the main purposes of sending a paper to a peer-reviewed conference is getting feedback about what other people think about your paper. If all the reviews one gets from a rejected paper is "a comma is missing in page 9", the sole purpose of sending a paper to a conference is defeated.
ReplyDeleteThe microsoft server
ReplyDeletehttp://msrcmt.research.microsoft.com/cmt/
has indeed been used for STOC (I think STOC 04), and I liked it way better than the standard system (in particular, the microsoft server allowed you to enter comments directly through a browser with a clear separation of comments to author and to PC). I don't know why they didn't use it again.
As for comments to authors, in addition to the bad system, I think part of the reason is the community culture (especially among more senior reviewers, in my experience). Discussions such as this one, and program chairs encouraging PC members to write everthing possible as comments to authors, is improving the problem.
If you want more feedback, try submitting to a European conference where there is typically far more use of subreferees who are experts and who are looking at maybe 1-3 papers each rather than a huge stack.
ReplyDeleteI think a "circle the wagons" attitude to criticism to STOC is the wrong approach and ultimately detrimental to those conferences. The level of comments for theory conferences in general (no reason to single out STOC) is dismally low compared to other fields. Suggestions such as "lower expectations" or "the system made me do it" are but excuses that fail to address the problem.
ReplyDeleteDuring the SODA business meeting Rajeev Raman and/or Adam Buchsbaum pointed out that ALENEX this year used software that by default sends comments to the authors. There was a subsequent noted increase in the length of the comments, without any major leakage. It was implcitly agreed that SODA should move to a "comments to authors" mode by default. We can only hope that other conferences will follow this lead.
As someone who submitted to both ALENEX+SODA this year, I found that the comments I got back from ALENEX were excellent. This was in stark contrast to those from SODA.
ReplyDeleteI would also agree that the justifications given by Paul Beame are weak. Other top CS conferences give excellent feedback. If they can manage it, why not SODA/STOC?
I have served on a number of PC's and there is nothing that remotely compares the workload of an individual PC member for those smaller conferences with that of SODA/STOC/FOCS. SODA is probably the worst in this regard in the sheer number of submissions per PC member which is why I think that Cliff Stein made the comments he did at SODA.
ReplyDeleteThe primary duty of a program committee is to select the best possible program for the community.
Good feedback on papers is extremely desirable; however, given the time constraints, if there is a choice between more carefully understanding the details of submitted papers in order evaluate them and typing in detailed comments then, sometimes, the latter must take a back seat.
One certainly should not expect comments explaining why a paper is accepted/rejected; that final discussion concerns relative merits of papers since the number of papers that can be presented at a conference is limited.
It is most unfortunate that good feedback that has been carefully typed in by PC members does not make it back to authors. Its existence was the point of my earlier message; I hope that someone will modify the system so that getting this back to authors is easier.
BTW: I have used a number of other systems for paper reviewing for other conferences and despite the clunkiness of some of the interfaces, as a PC member I've found that the ability to monitor progrss, discuss papers, and browse the submissions is actually better and easier with the system that is typically used for STOC/FOCS/SODA than with these other systems. It would be nice to get the best of both methods.
Paul Beame
SODA is probably the worst in [..] number of submissions per PC member.
ReplyDeleteHow about doubling the size of the PC and doubling the amount of comments? Plus frankly most papers are parceled out to subreferees and those tend to come back with detailed comments.
I wouldn't go as far as calling the sigact server the best software. Rather I'd say none of the other packages that I've used have stood up as clearly superior to the others. It is always a tradeoff in features.
About Paul Beame's tradeoff remark: For me writing detailed comments (or at least detailed handwritten notes) actually makes me understand the paper more :-)
ReplyDeleteI don't exactly get the high importance being given to confidential information leakage here. If your paper was compared to another submission that was accepted, you'd know anyway.
ReplyDeleteIf you were able to guess who the subreferee was, is it really that bad? I don't think people in the community are so vengeful that they would somehow get back to someone who rejected their paper on valid grounds. I agree anonymous referees are preferable, but lack of feedback seems to be a big price to pay for that.
How about the system requiring the subreferee to write at least as many characters in "comments to authors" as she writes in "comments to PC"?
How about doubling the size of the PC and doubling the amount of comments?
ReplyDeleteErrr.. twice zero is still zero.
More seriously, I think there are ways to increase the comments without substantially increasing the PC load. E.g. by increasing the expectations from subreferees. For the papers that are clear rejects, the subreferee comments should suffice.
I got only one comment from SODA '06 submission. To be fair, the quality of this comment is good (valid, helpful, and detailed).
ReplyDeleteI am wondering how many comments you got from SODA '06. If you also got only one, I would suspect there were some "software errors" (only sending the first one comment).
Here's a suggestion/challenge for Paul: log in to the STOC account and in the PC/DATA/REVIEWS_HTML directory search for papers with no comments to the authors. You can do this with:
ReplyDeletegrep -c BEGIN_COMMENT_FOR_AUTHOR * | grep ':0'
now grab at random a few of those review.X.phtml files with zero comments to authors and have a look at the "PC only" comments.
Do let us know if it is not the case that (a) most of those papers have comments and (b) large portions of those comments could have been passed to the authors.
Well, it will be quite a challenge for Paul, since he's local arrangements chair, not PC chair. (Is Jon Kleinberg reading this, by any chance?).
ReplyDeleteJan 31st has come and gone, and still the STOC comments have not been sent out. =)
ReplyDeleteI agree with a previous poster: if there are too many papers per committee member, then increase the size of the committee.
A point of reference: STOC '06 has 20 committee members, Eurocrypt '06 has 31. Eurocrypt gets roughly 200 submissions; how many did STOC get? (PS: comments from Crypto/Eurocrypt tend to be detailed and quite excellent.)
How about doubling the size of the PC and doubling the amount of comments?
ReplyDeleteA point of reference: STOC '06 has 20 committee members, Eurocrypt '06 has 31
What is being missed here is that, unlike conferences like Eurocrypt, members of SODA/STOC/FOCS PCs are prohibited from submitting papers to the conference. I don't see how we can double the PC size without changing this prohibition. Whenever the idea of allowing this has come up at business meetings it has been soundly defeated.
Here's a suggestion/challenge for Paul: log in to the STOC account
I am not on the PC so I do not have access to this information.
Paul Beame
The STOC comments for authors were to have gone out last night, I believe. I agree that the lack of feedback from the most recent SODA was abysmal even by STOC/FOCS/SODA standards but for STOC Jon has made much more effort than I'm used to seeing in getting the committee members to make their comments available to the authors. So�I'd be interested to see updates from the people who've been complaining here about lack of feedback.
ReplyDeleteActually the comments from STOC 2006 are much more detailed. Thanks to Jon.
ReplyDeleteThe typical feedback from STOC/FOCS/SODA relates to the importance of the problem or the approach (the more obfuscated the better I read somewhere).
ReplyDeleteIn the current system a "cartel effect" (replace prices with problem importance) is probable--( I can think of problems which dragged on dropping constants on and on to disappear into the blue-) which would be unhelathy for the community at large.
Obviously, the accepted papers, barring the few notable exceptions, reflect the bias of the PC members so adding more members may help.
I'm sure there are plenty of younger researchers who would happily serve on a STOC/FOCS committee (and write good reports!) even if it means they couldn't submit a paper...
ReplyDeleteSomehow I don't see this as the barrier.
SODA had over 300 attendees. It shouldn't be hard to find 40 people willing to serve in the program committee. Plus we can follow Muthu's tongue-in-cheek suggestion of making the most prolific submitters part of the PC thus further reducing the load on the PC members
ReplyDeleteDoubling PC size has a few other problems that I did not mention:
ReplyDelete1. Manageability. A PC chair simply can't effectively monitor the work of that many people over that short a time frame. All the conferences I know with much larger PC's than STOC/FOCS/SODA run highly distributed or two-tier PC's and do not prohibit PC members submitting papers. The two-tier model doesn't seem to me to be an improvement on the current STOC/FOCS/SODA model in which sub-refereeing is important but does not subtitute for PC member judgement. (I know others who disagree and say we should go to a two-tier model.)
2. Cost and Logistics: Current STOC/FOCS/SODA PC's make decisions at intensive face-to-face meetings at which the merits of papers are discussed thoroughly. (Such meetings are standard for the higher tier of two-tier conference PC's as well.) There are logistical problems that limit the size of any face-to-face meeting, let alone the cost that can be borne by the conference (about $40 of registration fees now goes to PC costs). For a while STOC had a policy of only electronic PC meetings to save money but these were abandoned because there was a great deal of dissatisfaction with the experience and the outcome among PC members and chairs. (My experience is that with all-electronic PC's, PC chairs can end up with inordinate influence on the outcome.) Such an approach can work well in more narrowly defined conferences in which one PC member's judgement can easily substitute for another's but it does not work well at a broad conference like STOC/FOCS.
One of the other benefits of a face-to-face meeting is that it is a great educational experience for everyone who serves, something that cannot be said for the all-electronic form. In addition to providing exposure and recognition for junior members and a way to contribute their opinions, it also is a great opportunity for them to hear the perspectives of other strong experienced people in the field. If you take a look at the composition of PC's over the last several years you will see that there is a large representation by excellent recent Ph.D.'s. Without a face-to-face meeting I am not sure that this would have been a good idea for them.
Paul Beame
All the conferences I know with much larger PC's than STOC/FOCS/SODA run highly distributed or two-tier PC's
ReplyDeletePaul, what do you mean by "highly distributed" PC's ? I was in a few "database" PC's (I am in a SIGMOD PC right now) and it did/does not seem that different from electronic-only PC's for theory conferences (modulo very recent developments such as asking authors for feedback etc). The main difference is that the access tends to be limited only to papers that one is reviewing, but that's because SIGMOD is paranoid about privacy. On the bright side, each PC member is reviewing <20 papers (even less this year, due to the multistage reviewing process).
Piotr
Eurocrypt has 31 PC members this year, has a one-tier format, and is having a face-to-face meeting...
ReplyDeleteExpanding committee members still doesnt take care of the "popularity contest" aspect mentioned in the very first comment. Anonymous submissions would help- of course some popularity aspect would get through via talks etc. There is sufficient amount of inbreeding in the PC which very likely narrows its outlook.
ReplyDeleteCurrent STOC/FOCS/SODA PC's make decisions at intensive face-to-face meetings at which the merits of papers are discussed thoroughly.
ReplyDeleteReally? I've never been part of program committee that met face-to-face and that includes some of the above conferences.
I also question the mindset here. Are we trying to find a way forward and fix perceived deficiencies or have we bought so much into the status quo that we now believe FOCS/STOC/SODA can't possibly be improved and we should limit our role to shooting down suggestions.
Paul, what do you mean by "highly distributed" PC's? I was in a few "database" PC's...SIGMOD...
ReplyDeleteThe main difference is that the access tends to be limited only to papers that one is reviewing
Piotr: This is exactly a situation in which the PC chair has a large amount of sway in the composition of the conference. One issue is that as things get down to the crunch, the cycle time on decisions is such that many PC members do not always have time to monitor and weigh in. The PC chair who controls what status appears on the website has much more power than individual members who may not (as in the case of SIGMOD) even know what the contents of all the papers are. Even if they do, at some level, we are all a bit like sheep because it is the easier path to go along and there is much less of a tendency to question proposals that already seem to have been made.
Paul Beame
Expanding committee members still doesnt take care of the "popularity contest" aspect mentioned in the very first comment.
ReplyDeleteProgram committees work extremely hard and honestly try to get the best program they can without bias. However, I still think that avoiding this is the most difficult issue that program committees face (much more so than issues with feedback).
There are simple things that can influence members of the PC. For example, if a PC member has seen a talk by someone on a submitted paper
or on a closely related paper then it is more likely that they are will understand the paper in detail (and papers are generally of such high quality that greater understanding will lead to more positive view). If the paper is by someone who has a long track record of important (and sound) contributions then one is somewhat more likely to give them the benefit of the doubt if there some uncertainty. (This is probably not a bad thing.)
The last issue is one of 'fashion': Areas in which there is significant progress tend to attract lots of other related work which tends to make them seem more important as a result. This can have valuable consequences for the field because it can make progress much more rapid in important areas. However, these attractive areas are not always as important in the long run as it appears at the time. Borderline papers in these more fashionable areas are somewhat more likely to get accepted than in other areas, often in part because the 'pressure' of the number of submissions is greater in those areas.
Paul Beame
One can quickly draw a long list of topics that had their "moment under the sun" during which papers were "overaccepted" so to speak. At various times in the last 4 decades or so this has included graph algorithms, sorting, DFAs, NP-complete results, complexity, on-line algorithms, computational geometry, parallel algorithms, randomized algorithms, fault tolerant computing, approximation (PCP) results, data streams, internet economics, metric embeddings, etc. This is in no way a criticism of those areas: no longer being the most popular person in highschool doesn't mean one is now a bad person.
ReplyDeleteI also agree that it is very difficult to find the right balance between what is hot and important and what is hot and not so important.
The Eurocrypt model seems to work quite well though even it requires improvement (~25 papers per PC member is not a PC of cake either).
ReplyDeleteFor STOC etc: Anonymous submissions, allow one submission per PC member (reviewed by a larger number of other PC members), double the size of PC, use better software...
If the paper is by someone who has a long track record of important (and sound) contributions then one is somewhat more likely to give them the benefit of the doubt if there some uncertainty. (This is probably not a bad thing.) ..
ReplyDeleteThis would an extra burden to someone who has not yet managed an elite reputation-- and particularly disappointing to graduate students working alone or with less elite advisors.
The PC chair who controls what status appears on the website has much more power than individual members who may not (as in the case of SIGMOD) even know what the contents of all the papers are.
ReplyDeleteRight, but we do not have to adopt that particular policy (restricted access to papers).
I agree that electronic meeting give somewhat more power to the chair. But in the electronic-only PC's for theory conferences that I served in, the discussions were very mild and PC chairs were very sensitive to people's objections, at any stage of the process.
Altogether, I think the choice between electronic and person-to-person meetings is mostly a matter of personal preferences.
Finally, note that one big advantage of electronic-only meetings is that all discussion is recorded electronically, and thus it is much easier to give a thorough feedback to the authors.
Piotr
This would an extra burden to someone who has not yet managed an elite reputation-- and particularly disappointing to graduate students working alone or with less elite advisors.
ReplyDeleteThis is known as the Matthew effect. That is, the rich get richer and the poor get poorer. Notice that in practice this amplifies differences, but doesn't change the total order.
I posted this once, but it did not seem to appear, so I am reposting. Sorry for duplicates, if any..
ReplyDelete-------------
The PC chair who controls what status appears on the website has much more power than individual
members who may not (as in the case of SIGMOD) even know what the contents of all the papers are.
Right, but we do not have to adopt that particular policy (restricted access to papers).
I agree that electronic meetings give somewhat more power to the chair. But in the electronic-only PC's for theory conferences that I served in, the discussions were very mild and PC chairs were very sensitive to people's objections, at any stage of the process.
Altogether, I believe the choice between electronic and person-to-person meetings is mostly a matter of personal preferences.
Finally, note that one big advantage of electronic-only meetings is that all discussions is recorded electronically, and thus it is much easier to give a thorough feedback to the authors.
Piotr
Also, why do I continually get the sense that 60-70% of a STOC acceptance is based on what might politely be called a "popularity contest"?
ReplyDeleteIf this is widely believed then one can simply reduce the number accepted papers (by 60%) --- and have satellite workshops for fashion areas. Alternately, increase the number of accepted papers (which might have other side effects).
I realize that what I wrote can easily be misconstrued. I did not mean to imply that a borderline paper by an author with lots of important and sound contributions is more likely to get in. (I think that the opposite has often been true - modulo the other points I made earlier.) The uncertainty I meant was with respect to correctness of claims. Submitted papers sometimes do not contain all the details so there can be uncertainty.
ReplyDeleteNormally a PC will try to verify what it can, but the ultimate responsibility for correctness lies with the authors. The bolder the claims the more the PC will check them independent of who is making them. However, I think it generally is easier to get convinced by someone who has track record of important and sound work.
Paul Beame
For the vast majority of submissions, correctness if not the issue. I don't really see any reason against "anonymous" submissions. If the PC, for some reason, feels the need to know the authors' names, then searching for the title on google will probably bring them up immediately.
ReplyDeleteOne advantage of anonymity, or, more accurately, of not having the authors' names prominently displayed, is that the reviewers are less prone to being influenced by that knowledge despite themselves.
From an anonymous STOC PC Member:
ReplyDeleteYes, the online PC review system used by STOC is awful, but it is a volunteer open-source effort. To whoever complained, please fix it!!!!
Make it easier for us to enter comments for the authors via a web
interface, for instance.
As for the allegations of a popularity contest, the bottom half or so (of accepted papers) are
really tough to judge, and while author names never come up,
"importance / interestingness of the question" always does, and one can
certainly argue that the "in crowd" PC members would be biased to agree
with other "in crowd" people as to importance or interestingness (how many
people would show up for the talk). It becomes hard to judge the bottom
half by 'technical coolness' alone...
Certainly an imperfect process, but I can't think of one that is better for such a large conference with so many subfields and submissions.
With all the complaints about the open-source review system being used, I wonder: does STOC really not have sufficient funds to pay to use the web review software used by most other conferences?
ReplyDeleteFrom a non-anonymous STOC PC member :)
ReplyDeleteI agree that the software used now is somewhat archaic and not perfect. But, it is not so bad either, and has a few advantages: it is quite reliable and you can access the data (at the very least, your own score card) locally and off-line.
The Microsoft CMT system (the only other system that I used) is more modern, definitely from the web era, but this comes at a price. E.g., it is *really* frustrating when the system announces "time out" when you are in the middle of writing the review (the text is lost).
(any resemblance to other product of the same company is unintentional and purely coincidential)
I also dont think you can use it off-line.
And finally, there are *features*: the messaging system generally ignores EOL characters, which makes your carefully articulated bullets look like garbage. And if you want to draw a counterexample using ascii graphics, good luck...
I know there are other reviewing systems out there. I am curious what people think about them.
Piotr
ReplyDeleteAs for the allegations of a popularity contest, the bottom half or so (of accepted papers) are
really tough to judge, and while author names never come up,
"importance / interestingness of the question" always does, and one can
certainly argue that the "in crowd" PC members would be biased to agree
with other "in crowd" people as to importance or interestingness (how many
people would show up for the talk). It becomes hard to judge the bottom
half by 'technical coolness' alone...
Certainly an imperfect process, but I can't think of one that is better for such a large conference with so many subfields and submissions
This indicates a good reason for either reducing the number of accepted papers or maybe increasing them -- !