tag:blogger.com,1999:blog-3722233.post115148969626044996..comments2021-12-01T13:41:42.544-06:00Comments on Computational Complexity: FOCS Accepts and a MovieLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger216125tag:blogger.com,1999:blog-3722233.post-37369250047776639032007-12-23T11:28:00.000-06:002007-12-23T11:28:00.000-06:00In early July 2006, I read this post and some of t...In early July 2006, I read this post and some of the following comments. Barely read it, skimmed really, and it made my tummy ache. About a week later I "quit" grad school. <BR/>Anonymous, your jealous rants had something to do with that - I just failed to understand how the reaction of sane people to "someone published a lot. he is young" could be a dozen comments modulating, qualifying, reducing, insulting...<BR/>When someone does something good, you congratulate them. Is that not correct?thttps://www.blogger.com/profile/05362291064620569539noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1170929962771446122007-02-08T04:19:00.000-06:002007-02-08T04:19:00.000-06:00Thanks, Mihai, your comment again confirms my susp...Thanks, Mihai, your comment again confirms my suspicion that in the area of computer science theory, networking and the privilege to get resources, (i.e., know people who control this area, get known by people who control this area, just like how mafia works,with due respect to mafia) count much much more than anything else. Is the problem solved meaningful? Who cares. I looked at FOCS papers each year and read them, but I don't see solving made-up problems, I mean, basically all of them, is in any sense, meaningful, impressive, or create positive value to the human civilization. <BR/><BR/>Re:<BR/>While at it, let me give you something to ponder. My undergrad career was made possible by Erik, who decided to fund a freshman to work on whatever he fancied (honestly, I had him convinced for maybe 1 year that my main interest is number theory). He continued to give me unconditional support (funds, university rule bending etc), even as it became clear that we are very incompatible researchers and the chances we could actually work together on a problem are virtually nil.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152813706323693532006-07-13T13:01:00.000-05:002006-07-13T13:01:00.000-05:00This comment has been removed by a blog administrator.Shiva Kintalihttps://www.blogger.com/profile/07853545928906483737noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152780310387587702006-07-13T03:45:00.000-05:002006-07-13T03:45:00.000-05:00I think "game theory" = selfish agents competing a...I think "game theory" = selfish agents competing as opposed to the PC converging to a social optimum.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152764020194500032006-07-12T23:13:00.000-05:002006-07-12T23:13:00.000-05:00What exactly is wrong with "game theory"?What exactly is wrong with "game theory"?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152759603794528882006-07-12T22:00:00.000-05:002006-07-12T22:00:00.000-05:00Why not have the members of the PC selected from t...<B>Why not have the members of the PC selected from the TENURED professors only?</B><BR/><BR/>There would be less "game theory" and less "mafia" complains in this case. Tenured faculty are more secure on their position. They don't care about playing games and in general care more about the science itself (as opposed to just publishing).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152719222331314842006-07-12T10:47:00.000-05:002006-07-12T10:47:00.000-05:00I am currently a PhD student, and I have been foll...I am currently a PhD student, and I have been following the complaints regarding PCs and accepting/rejecting papers for the last two years. I thought I'd post some of my thoughts, with a disclaimer: "What has been is what will be, and what has been done is what will be done; there is nothing new under the sun". Also, some of the suggestions have their flaws, which I hope I remember to mention.<BR/><BR/><BR/>(1) The size of program committees should be proportional to the number of submitted papers, and not decided before the submission deadline. This is hard to implement - but probably worth the while in order to give a more rational workload. Moreover, committee members should be allowed to submit - this will accelerate the science as a whole, which is probably more important than other considerations, and biasness (such as privacy) can be solved using software.<BR/><BR/>(2) Papers should be accepted/rejected in a more binary fashion. This means that first you decide whether the paper is accepted or not and only then begin to compare with other papers (in case it was accepted). The "upper-bound" due to time constraints is silly. It is more important to accept good papers then to ensure that one can attend all of the interesting (to him or her) talks. Once the number of accepted papers is determined, only then - arrange the talks as needed, where you can have the best results with no parallel sessions, and then some parallel sessions for the rest of the paper.<BR/><BR/><BR/>(3) - The number of reviewers should also be increased. We all know that a sampling process is as good as the size of the sample (and other parameters as well). In fact, it might be helpful to have a few experts and a few non-experts review the same paper. <BR/>The major problem with this suggestion is that some topics simply don't have enough experts. I have no solution for this one.<BR/><BR/>(4)Regarding feedback to authors - (4.a) I once asked a professor "why doesn't the program committee provide the authors the full reviews and discussion that was made regarding the paper (omitting names)?" The answer I received was that privacy is important to many people, and they would not give the same comments knowing the authors would see them. I can understand this, however, However, having all of the comments guarantees that the committee does its job (as pointed out by "Mr. Moore"), and in addition, the authors have a clear view on why their paper was not accepted, which in turn can maybe put the results in the right perspective for the author.<BR/><BR/>(4.b) I also think that the entire "protocol" of the reviewing process should be published (with some censorship by the PC-chair, as needed). This can give the entire community a better "feel" for what needs to be done to get a paper accepted, or even better (for the committee), when not to submit it.<BR/><BR/>(5) Regarding doubly-blinded submissions: I think that given the reasons above in favor or against, double-blinded submissions are a dominating strategy as opposed to non-anonymous submissions. Also, in regard to some thoughts mentioned above, it is NOT okay to assume something is correct because of the name of the author.<BR/><BR/><BR/>(6) Regarding the business meetings - I have attended a few. First, I don't believe that the people attending give good representation to the entire community. This must be solved - and votes should be doubly-blinded, oh, I mean anonymous.<BR/><BR/>I have some more thoughts, but the ones mentioned are the most important ones, I think.<BR/><BR/>I am hoping for some serious feedback - as I am probably wrong on many issues.<BR/><BR/>I thought of posting my name, but: (1) I am begging for anonymousity, so I will stick to it, and (2) I might be saying something I will regret in a few years...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152710296575176972006-07-12T08:18:00.000-05:002006-07-12T08:18:00.000-05:00Aggrawal, Kayal, and Saxena's "PRIMES is in P" is ...Aggrawal, Kayal, and Saxena's "PRIMES is in P" is based in significant part on earlier work by Aggrawal and Biswas that appeared in FOCS 99, although of course there are many new ides. It was published in the Annals only because one of the editors of that journal offered publication in the Annals essentially immediately after it was distributed on the internet. The submission rules for STOC restricting prior journal submission prevented them from submitting to STOC. However, Agrawal did present the work in a special session of FOCS 2002.<BR/><BR/>"PRIMES is in P" is a perfect example of results by authors from the FOCS/STOC/SODA community with the sensibilities of our community making contributions with much wider influence. The authors remain part of the FOCS/STOC/SODA community; for example, both Kayal and Saxena have recent FOCS and STOC papers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152586150430105792006-07-10T21:49:00.000-05:002006-07-10T21:49:00.000-05:00Mafias, wannabe mathematicians, only F/S count, so...Mafias, wannabe mathematicians, only F/S count, sour grapes, TCS is unlikely rotten ... what is it with this thread that seems to attract an unusual number of trolls?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152584631392315092006-07-10T21:23:00.001-05:002006-07-10T21:23:00.001-05:00In fact, I suspect that in fact most of them are w...<I>In fact, I suspect that in fact most of them are wannabe mathematicians in any case. Before I get flamed<BR/>just notice where the most "prestigious" recent result of TCS (Primes is in P) appears.<BR/>Not JACM, SICOMP or any other top CS journals but in the Annals. Ditto for other recent "breakthrough" results in metric space embeddings etc.</I><BR/><BR/>There is a much better way to explain this trend. CS people learn about results through conferences (notice that the examples you cite above all appeared in STOC/FOCS before journal publication). If you believe that your result might also be interesting and/or relevant to a wider community (mathematics, say) then it makes sense that the second forum for publication you choose would be mathematical.<BR/><BR/>For the metric embedding results, for instance, I believe the motivation for publishing in math journals is not as much to get "props" from the mathematicians, but instead because those communities are interested in the techniques and their applications to CS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152584621568141302006-07-10T21:23:00.000-05:002006-07-10T21:23:00.000-05:00In fact, I suspect that in fact most of them are w...<I>In fact, I suspect that in fact most of them are wannabe mathematicians in any case. Before I get flamed<BR/>just notice where the most "prestigious" recent result of TCS (Primes is in P) appears.<BR/>Not JACM, SICOMP or any other top CS journals but in the Annals. Ditto for other recent "breakthrough" results in metric space embeddings etc.</I><BR/><BR/>There is a much better way to explain this trend. CS people learn about results through conferences (notice that the examples you cite above all appeared in STOC/FOCS before journal publication). If you believe that your result might also be interesting and/or relevant to a wider community (mathematics, say) then it makes sense that the second forum for publication you choose would be mathematical.<BR/><BR/>For the metric embedding results, for instance, I believe the motivation for publishing in math journals is not as much to get "props" from the mathematicians, but instead because those communities are interested in the techniques and their applications to CS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152584506027793522006-07-10T21:21:00.000-05:002006-07-10T21:21:00.000-05:00I completely agree with the previous anonymous.I completely agree with the previous anonymous.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152581382218481842006-07-10T20:29:00.000-05:002006-07-10T20:29:00.000-05:00Theoretical computer science is a field where the ...Theoretical computer science is a field where the most valued end-products are theorems backed by mathematical proofs. Logically most TCS people should be in Math departments. In fact, I suspect that in fact most of them are wannabe mathematicians in any case. Before I get flamed <BR/>just notice where the most "prestigious" recent result of TCS (Primes is in P) appears.<BR/>Not JACM, SICOMP or any other top CS journals but in the Annals. Ditto for other recent "breakthrough" results in metric space embeddings etc. <BR/><BR/>So lets end this charade of FOCS/STOC and start treating conferences as places to meet and<BR/>exchange ideas as mathematicians tend to do. Get rid of the proceedings and publish anything worthwhile in journals. And in any case we all know that anything appearing in two-column format just does not cut it with mathematicians.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152556308265366922006-07-10T13:31:00.000-05:002006-07-10T13:31:00.000-05:00Uploading reviews of accepted papers creates more ...Uploading reviews of accepted papers creates more problems than it solves, since acceptance is based not just on reviews but also on discussions between committee members. After all, a sub-referee just gets to see the one paper, while the committee has a global view and is better placed to make decision.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152553001104969342006-07-10T12:36:00.000-05:002006-07-10T12:36:00.000-05:00I am a PhD student with some publications to my (a...I am a PhD student with some publications to my (and my co-authors) credit...<BR/><BR/>Most of the complaints are arising due to tiny reviews. The authors deserve a somewhat detailed review (even if it is by personal e-mail) of their rejected papers.<BR/><BR/>I don't think uploading reviews of the accepted papers on the F/S website harms anybody. Since, those reviews are hopefully positive and can only help the authors of accepted papers.<BR/><BR/>Also, if a wrong proof appears in the accepted paper, the reviewers should be able to find it with very high probability. The reviewers are supposed to be knowledgeable about the area and possess mathematical skills and background to "verify" the proof, (even if it took the authors an year to come up with the ideas and proofs).<BR/><BR/>I myself reviewed papers and found bugs and reported to the authors. This might be because I am a PhD student and have a learning incentive.<BR/><BR/>Later, If somebody comes back to the author with a valid bug in the accepted paper, the author should have a common sense to accept the blame and correct it if it can be corrected. The errata section of the proceedings can help him to submit the correction. If the bug is irrepairable then the author should have the courtesy to remove it from his CV and publications list. This will only increase respect for him/her in the community.<BR/><BR/>If we run after success and tenure at the expense of morals, then there is no difference between us and terrorists/sick-politicians.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152518337382154452006-07-10T02:58:00.000-05:002006-07-10T02:58:00.000-05:00I've been working on this field for nearly twenty ...<I><BR/>I've been working on this field for nearly twenty years and I've yet to run into an error in a published paper that was of any consequence. The biggest flaw I've ever found (totally unfixable, truth of result itself is in question) was, ironically, in a paper in the Journal of the ACM.<BR/></I><BR/><BR/>Um, Kapoor's shortest path algoritm on an arbitrary polyhedral surface (STOC99)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152512918065420862006-07-10T01:28:00.000-05:002006-07-10T01:28:00.000-05:00I don't have anything interesting to add to this t...I don't have anything interesting to add to this thread; but, thought of taking the credit for posting the 200th comment -- just in case, Prof. Fortnow has some prize for the 200th poster :-)<BR/><BR/>-Venkat ChakaravarthyAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152510744638274772006-07-10T00:52:00.000-05:002006-07-10T00:52:00.000-05:00It seems stupid to rank people by counting confer...It seems stupid to rank people by counting conference papers (even in STOC/FOCS/SODA) when there is a page limit in conferences and in most cases lots of proofs are just sketch and authors do not have any motivation to go through the much harder job of polishing the paper and produce the journal version which can be really checked. This is really bad for TCS to have such incomplete papers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152509331879261662006-07-10T00:28:00.000-05:002006-07-10T00:28:00.000-05:00Re: errors.I've heard various people suggest that ...Re: errors.<BR/><BR/>I've heard various people suggest that any conference paper with incomplete and sketchy proofs should be given a time limit to appear in journal form, say five years or so. <BR/><BR/>If no such version appears then the result is considered unproven and first person to submit a paper containing all proof gets the journal article to their name.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152507736631318022006-07-10T00:02:00.000-05:002006-07-10T00:02:00.000-05:00The problem with errors is a significant one. Shou...The problem with errors is a significant one. Shouldn't there be some mechanism to ensure that there is a later version of the paper in which the error is acknowledged and perhaps corrected, or at least errata in a subsequent conference proceedings? This is one case where adopting a laissez-faire attitude really hurts the reputation of the community.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152504443258211842006-07-09T23:07:00.000-05:002006-07-09T23:07:00.000-05:00I am signing out of this thread --signal/noise rat...I am signing out of this thread --signal/noise ratio is too low now. I hope the inside information I gave about the STOC/FOCS PC process was useful. There is a clear need to demystify it. Note that these conferences are run by professional organizations that do have elections etc. Please do vote in them (or become a candidate yourself). Also, come to F/S business meetings.<BR/><BR/>To Thomas Moore: realize that you have the power to get what you want. You can start a wiki website where people can post reviews they got from the F/S PCs on their submissions, and can solicit independent comments from others. As far as I know, you don't need any clearance from anybody to set up such a website. People can decide for themselves what level of "privacy" they like. Good luck! <BR/><BR/>Sanjeev AroraAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152496975775786482006-07-09T21:02:00.000-05:002006-07-09T21:02:00.000-05:00If you haven't run into any errors in TCS conferen...<I>If you haven't run into any errors in TCS conference proceedings, you must be working in a different area.</I> <BR/><BR/>I haven't run into any <B>major</B> errors. but have ran into lots of minor errors, including some of my own (one of them a particularly nasty typo from a careless search and replace).<BR/><BR/>I'm aware of two big errors found by someone else during the course of their research. The worst part was that after contacting the authors (which in both cases were big names with lots of publications) they hemmed and hawed rather than just admitting to being wrong.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152486390935270902006-07-09T18:06:00.000-05:002006-07-09T18:06:00.000-05:00If you haven't run into any errors in TCS conferen...If you haven't run into any errors in TCS conference proceedings, you must be working in a different area.<BR/><BR/>They are most definitely there.<BR/><BR/>I've seen fatal bugs in papers by Very Famous People. You kind of ask around "why is this paper on your CV but not on your webpage?" and you get the sheepish reply that it turns out to have unrecoverable bugs.<BR/><BR/>But hey, what can you expect from a conference system that considers itself a newspaper?<BR/><BR/>I will admit that I've even had a CCC paper with a bug that killed some side-results (most of it survives and is going to a journal... but will they review it more carefully?).<BR/><BR/>Those bugs are our own fault, not that of the reviewers... but from the grapevine I think that our paper and that of the VFPs I mentioned are just the tip of the iceberg. <BR/><BR/>So double-check on your own any result that you get out of a conference report. <BR/><BR/>And you have to wonder about the prestige CS puts upon conference publications...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152470521342769562006-07-09T13:42:00.000-05:002006-07-09T13:42:00.000-05:00I completely agree with Haarsh Ries. CS seems to b...I completely agree with Haarsh Ries. CS seems to be the only area in which conferences are more important than journals. Is it possible that everyone else is wrong and only computer scientists are right?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152459559554199752006-07-09T10:39:00.000-05:002006-07-09T10:39:00.000-05:00I think probabaly a good solution to all above pro...<I>I think probabaly a good solution to all above problems about referee process in conferences, mafias, etc is to run many parallel sessions in FOCS/STOC/SODA to reduce competition amd instead give more weights to the journal publications like all other sciences.</I><BR/><BR/>I agree that too much emphasis is given to conferences (as most other people I've talked about this do). I do not think it is realistic to expect radical change in this regard. A gradual loosening of the publishing bar in conferences might achieve this. Now careful what you wish for. At the end of this road lies conferences such as the ICM where distinction is granted by invitation to present, and all other tracks are open for the taking. If you think the current process is open to mafias, the invited talk system is doubly so.<BR/><BR/><I> Note that it is not good also for TCS that people refer to conference papers and base their results on something which can be completely incorrect (this happened a lot in our community). </I><BR/><BR/>I've been working on this field for nearly twenty years and I've yet to run into an error in a published paper that was of any consequence. The biggest flaw I've ever found (totally unfixable, truth of result itself is in question) was, ironically, in a paper in the Journal of the ACM.Anonymousnoreply@blogger.com