tag:blogger.com,1999:blog-3722233.post113200930380455038..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: Acceptance Rates versus CompetitivenessLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger20125tag:blogger.com,1999:blog-3722233.post-1132535526514589212005-11-20T19:12:00.000-06:002005-11-20T19:12:00.000-06:00Recently, a person who had claimed during the prev...Recently, a person who had claimed during the previous discussion that STOC/FOCS does not look down on algorithmic papers said during a conversation "algorithms is not theory". <BR/><BR/>Sadly, I don't think he's an isolated point. He represents a small but non-negligible percentage of the theory community who either thinks that algorithms is not theory or algorithms is "theory gone wrong". <BR/><BR/>I believe such views are on the way out, and have been on the wane since the mid 90s. However before that they were the dominant view of the STOC/FOCS program committees and even to date still some quite prominent members of STOC/FOCS PCs believe that SODA won't be an equal to STOC/FOCS until it has an equal percentage of fiendishly complicated complexity-style results. I think the term they use to describe them is "elegant", while others would describe them as "overwrought with technical challenges" instead.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132275424599170742005-11-17T18:57:00.000-06:002005-11-17T18:57:00.000-06:00Clair, I think the acceptance ratio is also quite ...Clair, I think the acceptance ratio is also quite related to SODA vs. FOCS/STOC issue, since the number of submissions in SODA is relatively high and in the same time SODA is one of the best theory conference.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132261003581934442005-11-17T14:56:00.000-06:002005-11-17T14:56:00.000-06:00Soda vs. Stoc/Focs has been discussed on this blog...Soda vs. Stoc/Focs has been discussed on this blog at length just recently, and we don't need to take up that discussion again. <BR/><BR/>We have no hard data and anonymous opinions are of tenuous value at best. Is everyone aware that they can post a non-anonymous comment by choosing from the "Choose an indentity" menu when they leave their comment?? Lance, perhaps you should give us your thoughts about anonymous vs. non-anonymous contributions...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132247345741501242005-11-17T11:09:00.000-06:002005-11-17T11:09:00.000-06:00As an algorithms researcher, I prefer getting a pa...As an algorithms researcher, I prefer getting a paper in SODA over STOC/FOCS. STOC/FOCS is definitely more complexity oriented and doesn't draw near as many algorithmic researchers as SODA.<BR/>Thus an algorithmic paper in SODA has a wider impact than one in FOCS/STOC.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132211503683422532005-11-17T01:11:00.000-06:002005-11-17T01:11:00.000-06:00This is ridiculous that someone compares SODA with...This is ridiculous that someone compares SODA with Complexity (SODA<BR/>has more than 450 submissions, I do not think that Complexity has<BR/>even 1/4 of this). Nowadays lots of people do not wait for<BR/>STOC if they have the results ready for SODA, esp. since STOC is<BR/>narrowly-centered on complexity. I have seen lots of papers in SODA<BR/>appearing in JACM or SICOMP which are surely more prestigious than<BR/>FOCS/STOC. I really don't think that SODA level is too different from STOC/FOCS level at least nowadays.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132211173500962472005-11-17T01:06:00.000-06:002005-11-17T01:06:00.000-06:00In short, for several other areas, people rank the...In short, for several other areas, people rank the "specialized conference" at the same level as STOC/FOCS. Hence many (junior and senior) people don't wait for STOC/FOCS.<BR/><BR/>In certain cases, people prefer to publish in the spcialized conferences as they provide better exposure to the relevant community.<BR/>So with certain types of papers, some people even wait for the specialized conference even if they think the paper is of high quality.<BR/><BR/>There's no reason anymore to treat SODA/PODC/SPAA/CG to be lower on the "food chain" than STOC/FOCS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132206599605010372005-11-16T23:49:00.000-06:002005-11-16T23:49:00.000-06:00I know many instances of (non-tenured) people subm...I know many instances of (non-tenured) people submitting high quality papers to SODA rather than STOC/FOCS simply because they solve a problem in the three months between April and July. If they think someone else is working on the problem, too, then obviously they will submit to SODA. The previous poster does not have a clue.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132170839664076892005-11-16T13:53:00.000-06:002005-11-16T13:53:00.000-06:00This last sentiment seems false to me. I do not kn...This last sentiment seems false to me. I do not know any algorithms researcher who, thinking his or her paper is of very high quality, would choose to submit to SODA _instead_ of FOCS or STOC.<BR/><BR/>I do know many senior (i.e. tenured) people who will submit a paper to SODA just because of the timing of the submission deadline instead of waiting for the next STOC. But the main point is that there is no conflict; no one has to decide between STOC/FOCS/SODA since the decisions for FOCS always come out before the SODA deadline.<BR/><BR/>The Complexity deadline, on the other hand, is usually in the neighborhood of the STOC deadline, so it makes sense that complexity researchers have to make tough decisions every November.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132151778092742942005-11-16T08:36:00.000-06:002005-11-16T08:36:00.000-06:00How do you know self-selection is not practiced in...How do you know self-selection is not practiced in other conferences as well?<BR/>How familiar are you, Lance, with the history of submissions and acceptences in top systems conferences like SOSP and SIGCOMM?<BR/>Have you seen the whole roster of submissions to any of these (or similar) conferences?<BR/><BR/>Did I see the phrase "self-serving" before?<BR/><BR/>The theory community should carefully do a reality check for itself: there is no reason to assume there are many so-so papers floating around and not submitted.<BR/>The real issue is that STOC has become too narrowly-centered on compelxity, driving algorithms to SODA and other topics to other conferences (which get lots and lots of submissions).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132101239149432682005-11-15T18:33:00.000-06:002005-11-15T18:33:00.000-06:00Did this topic come up becausesome one suffered at...Did this topic come up because<BR/>some one suffered at tenure or<BR/>promotion time because of the high<BR/>acceptance rates of theory <BR/>conferences?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132091107381591842005-11-15T15:45:00.000-06:002005-11-15T15:45:00.000-06:00One of the many possible reasons may be as follows...One of the many possible reasons may be as follows:<BR/><BR/>For a theory paper, every co-author get the credit (at least in theory). However, in almost every other CS subfields, only the first author get the majority of the credit (a student-advisor collabaration is an exception)<BR/><BR/>Therefore, for the folks to survive in non-theory CS subfields, they have to write more papers, to submit a paper again and again till accepted, ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132087918298095982005-11-15T14:51:00.000-06:002005-11-15T14:51:00.000-06:00That is true. On the other hand, after first STOC/...That is true. On the other hand, after first STOC/FOCS rejection, some people might decide not to submit their paper to those conferences again, so the "false negative" rate could be actually higher.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132085100377115912005-11-15T14:05:00.000-06:002005-11-15T14:05:00.000-06:00Claire's idea sounds good, although I would debate...Claire's idea sounds good, although I would debate the 'false negative' interpretation. The feedback from one conference can lead to a much better version submitted to a subsequent conference.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132081640142167632005-11-15T13:07:00.000-06:002005-11-15T13:07:00.000-06:00How can we gather evidence to test this self-selec...How can we gather evidence to test this self-selection theory?<BR/><BR/>Perhaps the program committee from STOC or FOCS two years ago could go through the list of papers which were then rejected, and find out what happened to them -- whether and where they eventually got published.<BR/><BR/>I would hope to see something along the following lines:<BR/>-submitted 250<BR/>-accepted 75<BR/>-accepted at a later STOC/FOCS 5<BR/>-accepted at Soda, Crypto, Complexity, Socg, or Podc (or some other similar "best conference in its subarea of theory" conference that I am forgetting) 100<BR/>-accepted at a "specialized workshop respected by people in that area" 40<BR/>-unpublished 25<BR/><BR/>To me, this would be evidence both of the accuracy of the decisions reached (only 5 false negatives) and of the self-selection process (most papers submitted are strong enough to be published in the best conference of their subarea).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132078909352350322005-11-15T12:21:00.000-06:002005-11-15T12:21:00.000-06:00It would be nice to be able to point to concrete e...It would be nice to be able to point to concrete evidence of self-selection (which is clearly going on). <BR/><BR/>Here's one possible measure: compare the acceptance rates of the generally acknowledged top conferences to those of the second tier conferences. The more similar they are, the more self-selection must be going on.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132076040857451972005-11-15T11:34:00.000-06:002005-11-15T11:34:00.000-06:00I'm always impressed with the high level of self-s...I'm always impressed with the high level of self-selection in theory conferences. In a recent large conference we had hundreds of submissions and less than 10% didn't belong there. All others had a reasonable shot at being accepted. In the end we had to select the top 30%, give or take a few, but save for that bottom 10% I would not have discouraged any of the other authors from submitting to the conference.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132068028352391112005-11-15T09:20:00.000-06:002005-11-15T09:20:00.000-06:00Lance -- I agree with you, or at least I would lik...Lance -- I agree with you, or at least I would like to. You didn't point out that this argument is important to the future of theory (or at least of young theoreticians), since people now use conference acceptance ratios to judge work quality. (Listing acceptance ratios on CVs is becoming common, a practice I detest.)<BR/><BR/>But really, isn't this argument painfully self-serving for our community? If we want to make the case that a FOCS/STOC paper with a 30% acceptance ratio is more significant than a conference in subfield XYZ with a 10% acceptance ratio, it seems like we need some evidence to back this argument up soundly. Otherwise, it just sounds like sour grapes. <BR/><BR/>MichaelMichael Mitzenmacherhttps://www.blogger.com/profile/06738274256402616703noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132028504677097782005-11-14T22:21:00.000-06:002005-11-14T22:21:00.000-06:00I think that one of the reasons why theory confere...I think that one of the reasons why theory conferences have low acceptance rates, is, as you point out: self-selection. Authors judge for themselves if their paper is good or not for submission. I think that this is in large part because submission is not anonymous, and if people submit nonsense, the reviewers will know who submitted that nonsense.<BR/><BR/>On on the other hand, conference such as SIGCOMM, SOSP, and several systems conferences have anonymous submissions. Thus, people can submit nonsense (which will never get accepted anyway), and get away with it. They do so thinking, "it won't get in, but I'll get some feedback from the committee anyway". That increases the number of submissions, and lowers acceptance rates.<BR/><BR/>2006 sees CRYPTO going non-anonymous. I'll bet there is a fall in the total number of submissions this year :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132018196080286622005-11-14T19:29:00.000-06:002005-11-14T19:29:00.000-06:00In my area, software engineering, there are four k...In my area, software engineering, there are four kinds of papers:<BR/><BR/>(1) good papers that get published; (2) bad papers that get published; (3) good papers that don't get published; and (4) bad papers that don't get published.<BR/><BR/>It seems "a good" paper has a 50-50 chance of actually making it.Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1132014209547645632005-11-14T18:23:00.000-06:002005-11-14T18:23:00.000-06:00Was this prompted by something in particular? As a...Was this prompted by something in particular? As a contrast, I think cryptography conferences tend to have a much lower acceptance rate than FOCS/STOC. Maybe we aren't doing a good enough job of pre-sorting submissions? or it could be that several distinct communities submit to the same conference sometimes.Anonymousnoreply@blogger.com