tag:blogger.com,1999:blog-3722233.post1312083224975038807..comments2024-03-18T17:27:11.613-05:00Comments on Computational Complexity: Meta Comment on FOCS/STOC commentsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger33125tag:blogger.com,1999:blog-3722233.post-45362137836859345302007-05-05T13:01:00.000-05:002007-05-05T13:01:00.000-05:00I guess that i'm not saying something new -- sorry...I guess that i'm not saying something new -- sorry but I don't have time to read all the previous comments.<BR/><BR/>there are many arguable ways to improve the accpet/reject/review/PC/ mechanism. <BR/>The simplest and yet satisfactory way is to let the reviewrs to see others' review, and update it accordingly. <BR/><BR/>It might be the case that the old versions might be saved in the stoc/focs site -- just to encourage originality ....Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85862635692123097312007-05-01T04:11:00.000-05:002007-05-01T04:11:00.000-05:00thank you very very much thank you very very nıce....thank you very very much thank you very very nıce...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43003467158239671922007-04-26T01:28:00.000-05:002007-04-26T01:28:00.000-05:00I don't understand something here. How come math p...<I>I don't understand something here. How come math people do publish papers, although they are not conference driven? <BR/>By the above logic, either they wouldn't publish (which is false), or CS people all have different personality than all math people. I don't see any evidence supporting this. <BR/></I><BR/><BR/>Not only is the personality of the field different, but the people themselves are in fact very different. CS is a young field. While there are some big questions and some theory-building that takes place, a large part of the research is problem-solving driven rather than theory-building driven. Also, there is a much larger connect with the real-world. Due to both these factors, the field is much more fast-moving.<BR/><BR/>The other aspect is the interactions. The collaboration graph in CS is significantly denser than that in math. Conferences are a focal point where many of these collaborations begin.<BR/><BR/>The personality of the papers itself is also very different from math. Most papers give some motivation for the problem being studied, give an outline of the techniques used, and usually try to give some intuition for the proofs. This, I think, certainly benefits the community, and happens in a large part due to the conference review process---you have the convince three PC members who are not necessarily experts in the subarea that this is a valuable contribution, which takes more work than convincing three journal reviewers who are intricately familiar with the subtle technical details of all papers in the subarea. As a result of this, a much larger audience can understand the work. Other than the obvious benefits, this significantly helps techniques from one subarea to be used in solving problems in other subareas. It is no surprise then that quite a few open problems in math have been solved by CS people, and proofs of many theorems have been considerably simplified by CS people.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53707145569185614032007-04-25T07:38:00.000-05:002007-04-25T07:38:00.000-05:00PC sizes have increased in recent times. PC sizes ...<I>PC sizes have increased in recent times. </I><BR/><BR/>PC sizes have crawled from an average of 15 around 1995 to an average of 18 today. <BR/><BR/><I> Second, it is already difficult to have a global view of the submitted papers to make reasonable decisions. Increasing the size will make this harder.</I><BR/><BR/>As a PC member I read 45 papers out of 275 submissions (16%). If we increase the PC size to 25 then the load is 33 papers out of 275 (12%). You mean to tell us that the 12 papers in the difference are critical in having a global view of the submitted papers? I don't buy it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89592897755310148432007-04-25T06:02:00.000-05:002007-04-25T06:02:00.000-05:00Remember Perelman?if Perelman was a CS guy he sure...Remember Perelman?<BR/><BR/>if Perelman was a CS guy he surely would write dozens of FOCS papers like "5n circuit lower bound for Clique".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59737424658666551012007-04-24T22:45:00.000-05:002007-04-24T22:45:00.000-05:00As a rough point of comparison, FOCS/STOC seem to ...As a rough point of comparison, FOCS/STOC seem to get about 300 submissions and have roughly 20 PC members, while Crypto/Eurocrypt get about 200 submissions and have roughly 30 PC members.<BR/><BR/>Assuming each papers is assigned to 3 PC members, this means 45 papers/PC member for the former as compared to 20 papers/PC member for the latter. This is a huge difference!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41195338456339063672007-04-24T22:21:00.000-05:002007-04-24T22:21:00.000-05:00PC sizes have increased in recent times. There are...PC sizes have increased in <BR/>recent times. There are two<BR/>counter arguments to increasing<BR/>the PC size much further. First,<BR/>this deprives the conference of<BR/>potential submissions from <BR/>PC members. Second, it is<BR/>already difficult to have a global<BR/>view of the submitted papers <BR/>to make reasonable decisions.<BR/>Increasing the size will make<BR/>this harder.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61534930006241903232007-04-24T19:20:00.000-05:002007-04-24T19:20:00.000-05:00A concrete suggestion: increase the size of the PC...<I>A concrete suggestion: increase the size of the PC.</I><BR/><BR/>This makes perfect sense, but it won't happen. I've seen members of the community which often serve in STOC/FOCS PCs argue for this and even they get nowhere.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43490623655660907132007-04-24T18:45:00.000-05:002007-04-24T18:45:00.000-05:00A concrete suggestion: increase the size of the PC...A concrete suggestion: increase the size of the PC. This would have the effects of:<BR/><BR/>1. increasing community participation<BR/><BR/>2. reducing load on PC members, theoretically leading to better reviews<BR/><BR/>3. increasing representation of certain areas (also leading to better reviews in some areas)<BR/>I don't really see any downsides. The only one I have heard is that people don't serve because they can't submit papers. But (1) why not allow 1 submission per PC member? and (2) even without implementing the first suggestion I am SURE there are plenty of people who would happily serve on the committee anyway.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70100819417750734502007-04-23T14:32:00.000-05:002007-04-23T14:32:00.000-05:00If we stoped writing conference paper and started...If we stoped writing conference paper and started to reward journal paper like mathematicians do,<BR/>somebody in east europe must have solved<BR/>the P-NP problem long time ago, but then<BR/>theoreticians would be paid like mathematicians, which<BR/>nobody here likes.<BR/>Remember Perelman?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24838692059506317922007-04-23T06:16:00.000-05:002007-04-23T06:16:00.000-05:00The idea of "fixing" STOC/FOCS is rather quixotic....The idea of "fixing" STOC/FOCS is rather quixotic. It is hard to make a stronger case than that for increasing somewhat the number of STOC/FOCS acceptances, yet the number hasn't budged much in fifteen years. Think about it, the data is incontrovertible as the TCS community has grown substantially in size, both in NorthAmerica and worldwide and the change is rather minor (a minor increase in acceptances), still it makes no difference and those conferences go merrily along at the same size as before (so does SCG for that matter).<BR/><BR/>For better or for worse, the solution to a problem with a conference is to create another conference. For example, since STOC/FOCS refused to grow we now have many other conferences of similar quality (SCG, LICS, SODA, etc) filling in the gaps.<BR/><BR/>If Vijay thinks a conference with video submissions would be better (judging from SIGGRAPH, I doubt it) then he should go ahead and create his own. <BR/><BR/>p.s. This is not a "love it or leave it" thing. It is just a pragmatical observation.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87009653576471466162007-04-23T00:53:00.000-05:002007-04-23T00:53:00.000-05:00There is some hand-wringing about 'randomness' in ...There is some hand-wringing about 'randomness' in the acceptance of 'borderline' papers at STOC/FOCS. Here are some factors that I have seen play a big role in acceptance/rejection for, say, the last 20 papers.<BR/><BR/>The biggest factor that committees go for in these borderline papers, one that I have not seen discussed in previous postings, is 'novelty'. This can be very different from some abstract notion of 'paper quality'. Novelty may be in the problem definitions or the techniques. At the borderline, committees will tend to choose papers with something particularly novel over safe papers that have good solid results that are similar in style to others at the conference. The feeling often is that it advances the field the most for the community as a whole to learn about novel ideas. This has an element of risk. In some cases papers are less novel than they appear or the novelty doesn't really lead anywhere. In other cases it can open up huge new areas. <BR/><BR/>However, even novelty will not be enough if a paper is particularly poorly organized or hastily written. One of the difficulties with novel ideas is that people are not always coherent about explaining them the first time around. Overhyping novelty also has a way of turning program committees off. On the flip side, sometimes committees can get confused by novel definitions and mistake the claimed novelty for overhype.<BR/><BR/>In any given year there will be fairly targeted research areas that attract ten, fifteen, or even twenty papers. In this case many papers will sound a lot like many other papers, in particular other papers ranked higher that have already been accepted. It can be tricky to tease apart how to rank the middle of the pack among this large number of closely-related papers since it is often a matter of taste. The problem is that if your paper loses within its popular area you are not going to win many novelty points when the borderline decisions come around if yours would be the n-th paper in the area. Exactly where a paper ranks in such a group can have a certain amount of randomness in it. (Note that from the committee's point of view small reversals in ranking in a group where differences are small has minimal impact on the quality of the conference, even though committees try to do this optimally.) <BR/><BR/>The toughest decisions are for papers in areas that typically have few attendees and submissions and where the committee has few members with expertise. A critical factor in acceptance can be whether the paper is written in a way that might make it accessible to a wider audience, or attempts to place the results in context. This is not generally an issue with most of the areas that people have mentioned such as geometry or data structures, but it is an issue for logic.<BR/><BR/>All else being equal, authors who already are represented among the accepted papers are somewhat less likely to have another borderline paper selected.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41830944085781007212007-04-22T19:15:00.000-05:002007-04-22T19:15:00.000-05:00On the positive side, conferences are more popular...On the positive side, conferences are more popular in CS probably means there is a lot more collaboration.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28215310873585375352007-04-22T11:56:00.000-05:002007-04-22T11:56:00.000-05:00Are the papers mostly good?Yes, but the converse i...<I>Are the papers mostly good?</I><BR/><BR/>Yes, but the converse is not true: not all the good papers make it in yet many in the field act as if they did.<BR/> <BR/><I>Is their a Name-School-bias? Is their a Name-person-bias?</I><BR/><BR/>Yes, but not as big as most people think (see SIGMOD stats). Still, anonymous submissions would be a step in the right direction. By removing bias as well as the *appearance* of bias.<BR/><BR/><I>Is their an area-bias? </I><BR/><BR/>Yes. STOC/FOCS claim to cover all of TCS but clearly they don't. First, there are areas off the list of topics, second, certain areas are automaticaly granted a lesser status and hence have a higher threshold to cross. Top papers in any area are accepted more or less fairly. Is the next fuzzy bunch in which there seems to be a bias towards complexity style results and/or technical proofs.<BR/><BR/><I>Is their a Hot-area-bias? </I><BR/><BR/>Absolutely yes. The hot area changes over time though, sometimes year over year.<BR/> <BR/><I>Is their a bias towards novel or hard techniques? </I><BR/><BR/>Some in the field are infatuated with technical difficulty. Just go back and read the archives of this blog to see how many people confuse difficulty with quality.<BR/><BR/><I>Aside from the clearly good and clearly bad papers, is it random? Is even determining clearly good and clearly bad also random?</I><BR/><BR/>Worse, it is not random but biased on the wrong parameters. One possible way to fix this is to select the bottom 10-20% of the papers at random from a group which includes those plus the top 10-20% rejected papers. This would erase non-quality biases while keeping quality more or less the same.<BR/><BR/><I>Are there many very good papers that do not get in?</I><BR/><BR/>*Very* good? No. Are there many papers which match the bottom half in quality that do not get in? YES!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52433351721753325222007-04-22T08:56:00.000-05:002007-04-22T08:56:00.000-05:00To Anon 14:Then the deadline-driven system should ...To Anon 14:<BR/>Then the deadline-driven system should be replaced by some other system for (reviewed) timely publication. In CS, it is important to publish the result as soon as you obtain it in order to prevent inventing the wheel, because too many researchers work on the same problem in the same direction simultaneously.edwardahirschhttps://www.blogger.com/profile/18094179693219521111noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44981070222082242232007-04-22T08:32:00.000-05:002007-04-22T08:32:00.000-05:00What I meant in comment 14# above was that it is b...What I meant in comment 14# above was that it is better to switch from a system that is "deadline oriented" (i.e., highly rewards publishing a terrible amount of papers), into a system that rewards quality over quantity. <BR/>This will enable more people to study fundamental problems in a timely manner (and not having in the meantime to publish a lot of less significant papers).<BR/><BR/>I suspect that (at least one of the reasons that) the fundamental problems of TOC will not be solved, or even partially solved, in the near future, is that not many professional scholars investigate these problems seriously, due to their urge to publish many papers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54851279635555302962007-04-22T08:07:00.000-05:002007-04-22T08:07:00.000-05:00Anon 14 wrote:I believe (though, I have no evidenc...Anon 14 wrote:<BR/><I>I believe (though, I have no evidence, of course), that the progress in resolving these problems, and thus the progress in our field, would be faster if the TOC community would conform to the standards of math research (as you described it).</I><BR/><BR/>I am not sure. There are two differences:<BR/>(1) much less mature field;<BR/>(2) many more active researchers.<BR/><BR/>CS is currently able to progress faster just because it is less studied and less deep sights are required. Replacing journals by conferences would not speed up math, but they still can (or they can't already?) keep CS progressing faster.<BR/><BR/>There is a crisis of the lack of refereeing resources due to (2), but otherwise probably conferences are still very suitable for CS.edwardahirschhttps://www.blogger.com/profile/18094179693219521111noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49126031172211497402007-04-22T07:38:00.000-05:002007-04-22T07:38:00.000-05:00Edward,I don't see any reason why CS should invent...Edward,<BR/><BR/>I don't see any reason why CS should invent the wheel here. <BR/>Fundamental questions in complexity theory are of a pure mathematical nature. <BR/>I believe (though, I have no evidence, of course), that the progress in resolving these problems, and thus the progress in our field, would be faster if the TOC community would conform to the standards of math research (as you described it).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69692416437668209512007-04-22T06:02:00.000-05:002007-04-22T06:02:00.000-05:00> either they wouldn't publish (which is false),Th...> either they wouldn't publish (which is false),<BR/><BR/>They would, though at a different pace and in a different form. Slowing down the publication process mean fewer papers, but the published papers are of better quality, though at the price of slowing down the progress as well.<BR/><BR/>Concerning the personalities...math people do have many more single-authored papers than CS people, don't they?edwardahirschhttps://www.blogger.com/profile/18094179693219521111noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42612504552967221422007-04-22T05:56:00.000-05:002007-04-22T05:56:00.000-05:00If we didn't have deadlines it almost seems that n...<I>If we didn't have deadlines it almost seems that no papers would get written</I><BR/><BR/>I don't understand something here. How come math people do publish papers, although they are not conference driven? <BR/>By the above logic, either they wouldn't publish (which is false), or CS people all have different personality than all math people. I don't see any evidence supporting this.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64562045593594505732007-04-22T02:28:00.000-05:002007-04-22T02:28:00.000-05:00Is the community really driven by these conference...<I> Is the community really driven by these conferences?</I><BR/><BR/>Yes, but probably not in the way that Bill meant the question. CS, unlike Math say, is incredibly deadline driven. If we didn't have deadlines it almost seems that no papers would get written. Deadlines gives us an excuse to break away from the constant interruptions of classes/committee work and finally concentrate on research. They also are a great opportunity for peer pressure: when many of your peers are focused on a major deadline, you'll feel left out if you aren't too. Overall, without the pressure of major conference deadlines there would simply be a lot less research produced and a lot less quality work, at least in CS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90271937641018864032007-04-21T18:08:00.000-05:002007-04-21T18:08:00.000-05:00Kamal, just to say that it is great to have someon...Kamal, just to say that it is great to have someone in the community as brutally honest as you are. Too often unethical behavior remains secret because of a presumed need for "collegiality.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70506960047793369452007-04-21T16:51:00.000-05:002007-04-21T16:51:00.000-05:00Dear Bill (and Blogowner),I think having an interf...Dear Bill (and Blogowner),<BR/><BR/>I think having an interface that looks like USENET group will be better. Then all the anony"mouses" will reply to the proper thread, rather than beginning with "to Anonymous 1234".<BR/><BR/>This is particularly true as some of the recent posts seem to be more of <I>"what do you think of ..."</I> types.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42362098455575919802007-04-21T11:31:00.000-05:002007-04-21T11:31:00.000-05:00Regarding second point on the second list."Prove t...Regarding second point on the second list.<BR/><BR/>"Prove that it really is a problem. The proof has to use novel or difficult techniques."<BR/><BR/>Why do we want the prood to be difficult. I think "difficult" is a bug and not a feature. I will take a big objection to it and claim that this is a very big part of the problem. It is rewarding complexity over simplicity.<BR/><BR/>There must be many papers, but I have seen at least two stoc/focs papers where a complicated proof was submitted when a trivial proof existed. For one of the paper, the author of the existing papers co-operated and liked the trivial proof. So the trivial proof also appeared in Stoc/Focs. This kind of authors are good who augmented the scientific discovery process. They do not take advanatge of the inherent problems with Focs/Stoc, i.e., do not game the system.<BR/><BR/>In the other paper, the authors hated the trivial proof. They did not co-operate. One of their complicated proof was incorrect but they kept sending incorrect versions until the Stoc deadline, knowingly. The stoc happened the trivial proof was submitted to the conference. The authors went to the extent that they raised the conflict of interest and indirectly criticized the trivial proof. There was some professional relationship but no personal relationship to require conflict of interest.<BR/><BR/>Of course in the journal version on the website, the incorrect proof is removed, quitely. The trivial proof is termed "simplification" of their original proof. And their talks do not even mention the simplification but mention that the original proof is "magical", as if being "magical" is a feature and not a bug.<BR/><BR/>This set of authors take the advantage of inherent unavoidable problems in Stoc/Focs review, even after the review process. They game the system, rather successfully, and some are even rewarded member of our community.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64481148411416411732007-04-21T11:07:00.000-05:002007-04-21T11:07:00.000-05:00Check up the difference between 'their' and 'there...Check up the difference between 'their' and 'there'.Anonymousnoreply@blogger.com