tag:blogger.com,1999:blog-3722233.post113872012605453905..comments2024-03-18T23:13:09.570-05:00Comments on Computational Complexity: STOC PapersLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger50125tag:blogger.com,1999:blog-3722233.post-1139498618128580902006-02-09T09:23:00.000-06:002006-02-09T09:23:00.000-06:00As for the allegations of a popularity contest, th...<I><BR/>As for the allegations of a popularity contest, the bottom half or so (of accepted papers) are<BR/>really tough to judge, and while author names never come up,<BR/>"importance / interestingness of the question" always does, and one can<BR/>certainly argue that the "in crowd" PC members would be biased to agree<BR/>with other "in crowd" people as to importance or interestingness (how many<BR/>people would show up for the talk). It becomes hard to judge the bottom<BR/>half by 'technical coolness' alone...<BR/><BR/>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</I><BR/><BR/>This indicates a good reason for either reducing the number of accepted papers or maybe increasing them -- !Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139100045251250322006-02-04T18:40:00.000-06:002006-02-04T18:40:00.000-06:00From a non-anonymous STOC PC member :)I agree that...From a non-anonymous STOC PC member :)<BR/><BR/>I 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. <BR/><BR/>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).<BR/><BR/>(any resemblance to other product of the same company is unintentional and purely coincidential)<BR/><BR/>I also dont think you can use it off-line. <BR/>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...<BR/><BR/>I know there are other reviewing systems out there. I am curious what people think about them.<BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139097951358186322006-02-04T18:05:00.000-06:002006-02-04T18:05:00.000-06:00With all the complaints about the open-source revi...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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139093091721602592006-02-04T16:44:00.000-06:002006-02-04T16:44:00.000-06:00From an anonymous STOC PC Member:Yes, the online P...From an anonymous STOC PC Member:<BR/><BR/>Yes, the online PC review system used by STOC is awful, but it is a volunteer open-source effort. To whoever complained, please fix it!!!!<BR/>Make it easier for us to enter comments for the authors via a web<BR/>interface, for instance.<BR/><BR/>As for the allegations of a popularity contest, the bottom half or so (of accepted papers) are<BR/>really tough to judge, and while author names never come up,<BR/>"importance / interestingness of the question" always does, and one can<BR/>certainly argue that the "in crowd" PC members would be biased to agree<BR/>with other "in crowd" people as to importance or interestingness (how many<BR/>people would show up for the talk). It becomes hard to judge the bottom<BR/>half by 'technical coolness' alone...<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139017025586460682006-02-03T19:37:00.000-06:002006-02-03T19:37:00.000-06:00For the vast majority of submissions, correctness ...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. <BR/><BR/>One 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139012686164536842006-02-03T18:24:00.000-06:002006-02-03T18:24:00.000-06:00I realize that what I wrote can easily be misconst...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. <BR/><BR/>Normally 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.<BR/><BR/>Paul BeameAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139012011347366542006-02-03T18:13:00.000-06:002006-02-03T18:13:00.000-06:00Also, why do I continually get the sense that 60-7...<I>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"? </I><BR/><BR/>If 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).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139007248623835632006-02-03T16:54:00.000-06:002006-02-03T16:54:00.000-06:00I posted this once, but it did not seem to appear,...I posted this once, but it did not seem to appear, so I am reposting. Sorry for duplicates, if any..<BR/>-------------<BR/><BR/><EM>The PC chair who controls what status appears on the website has much more power than individual <BR/>members who may not (as in the case of SIGMOD) even know what the contents of all the papers are.<BR/></EM><BR/><BR/>Right, but we do not have to adopt that particular policy (restricted access to papers).<BR/><BR/>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.<BR/><BR/>Altogether, I believe the choice between electronic and person-to-person meetings is mostly a matter of personal preferences.<BR/><BR/>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.<BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139005267272219402006-02-03T16:21:00.001-06:002006-02-03T16:21:00.001-06:00This would an extra burden to someone who has not ...<I>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.</I><BR/><BR/>This is known as the <A HREF="http://en.wikipedia.org/wiki/Matthew_effect" REL="nofollow">Matthew effect</A>. 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1139005265705183592006-02-03T16:21:00.000-06:002006-02-03T16:21:00.000-06:00The PC chair who controls what status appears on t...<EM> 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.</EM><BR/><BR/>Right, but we do not have to adopt that particular policy (restricted access to papers). <BR/><BR/>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. <BR/><BR/>Altogether, I think the choice between electronic and person-to-person meetings is mostly a matter of personal preferences.<BR/><BR/>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. <BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138996799850872732006-02-03T13:59:00.000-06:002006-02-03T13:59:00.000-06:00If the paper is by someone who has a long track re...<I> 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.) ..</I><BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138996275453742612006-02-03T13:51:00.000-06:002006-02-03T13:51:00.000-06:00The Eurocrypt model seems to work quite well thoug...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). <BR/><BR/>For 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...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138996220223884822006-02-03T13:50:00.000-06:002006-02-03T13:50:00.000-06:00One can quickly draw a long list of topics that ha...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.<BR/><BR/>I 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138988154754244232006-02-03T11:35:00.000-06:002006-02-03T11:35:00.000-06:00Expanding committee members still doesnt take care...<I>Expanding committee members still doesnt take care of the "popularity contest" aspect mentioned in the very first comment.</I><BR/><BR/>Program 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).<BR/><BR/>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<BR/>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.) <BR/><BR/>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.<BR/><BR/>Paul BeameAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138986211740389962006-02-03T11:03:00.000-06:002006-02-03T11:03:00.000-06:00Paul, what do you mean by "highly distributed" PC'...<I>Paul, what do you mean by "highly distributed" PC's? I was in a few "database" PC's...SIGMOD...<BR/><BR/>The main difference is that the access tends to be limited only to papers that one is reviewing</I><BR/><BR/>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.<BR/><BR/>Paul BeameAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138983608229677322006-02-03T10:20:00.000-06:002006-02-03T10:20:00.000-06:00Current STOC/FOCS/SODA PC's make decisions at inte...<I>Current STOC/FOCS/SODA PC's make decisions at intensive face-to-face meetings at which the merits of papers are discussed thoroughly.</I><BR/><BR/>Really? I've never been part of program committee that met face-to-face and that includes some of the above conferences.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138979863170371122006-02-03T09:17:00.000-06:002006-02-03T09:17:00.000-06:00Expanding committee members still doesnt take care...Expanding 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138974029169002572006-02-03T07:40:00.000-06:002006-02-03T07:40:00.000-06:00Eurocrypt has 31 PC members this year, has a one-t...Eurocrypt has 31 PC members this year, has a one-tier format, and is having a face-to-face meeting...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138950945763959282006-02-03T01:15:00.000-06:002006-02-03T01:15:00.000-06:00All the conferences I know with much larger PC's t...<EM> All the conferences I know with much larger PC's than STOC/FOCS/SODA run highly distributed or two-tier PC's </EM><BR/><BR/>Paul, 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). <BR/> <BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138948244786622282006-02-03T00:30:00.000-06:002006-02-03T00:30:00.000-06:00Doubling PC size has a few other problems that I d...Doubling PC size has a few other problems that I did not mention:<BR/><BR/>1. 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.)<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>Paul BeameAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138943697252530602006-02-02T23:14:00.000-06:002006-02-02T23:14:00.000-06:00SODA had over 300 attendees. It shouldn't be hard ...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 membersAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138920249894182152006-02-02T16:44:00.000-06:002006-02-02T16:44:00.000-06:00I'm sure there are plenty of younger researchers w...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...<BR/><BR/>Somehow I don't see this as the barrier.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138914564955277742006-02-02T15:09:00.000-06:002006-02-02T15:09:00.000-06:00The typical feedback from STOC/FOCS/SODA relates ...The typical feedback from STOC/FOCS/SODA relates to the importance of the problem or the approach (the more obfuscated the better I read somewhere). <BR/><BR/>In 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.<BR/><BR/>Obviously, the accepted papers, barring the few notable exceptions, reflect the bias of the PC members so adding more members may help.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138914069630612112006-02-02T15:01:00.000-06:002006-02-02T15:01:00.000-06:00Actually the comments from STOC 2006 are much more...Actually the comments from STOC 2006 are much more detailed. Thanks to Jon.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1138909123623757362006-02-02T13:38:00.000-06:002006-02-02T13:38:00.000-06:00The STOC comments for authors were to have gone ou...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.Anonymousnoreply@blogger.com