tag:blogger.com,1999:blog-3722233.post113379702149195730..comments2021-12-06T22:20:37.890-06:00Comments on Computational Complexity: The Day AfterLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-1133865790339273842005-12-06T04:43:00.000-06:002005-12-06T04:43:00.000-06:00To many people in our field are keeping their resu...To many people in our field are keeping their result secret after submission to a conference or a journal. I think sending the paper to coRR before submission to a conference or a journal should be mandatory.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133863084924647632005-12-06T03:58:00.000-06:002005-12-06T03:58:00.000-06:00Re: Jonathan Katz's commentCrypto has eprint, (epr...Re: Jonathan Katz's comment<BR/><BR/>Crypto has eprint, (eprint.iacr.org), with its own problems. I personally would prefer eprint to borrow from ECCC the possibility to keep up old versions of the submissions, and to link comments to the submissions. Keeping old versions also helps to time-stamp the results.<BR/><BR/>This year, there are almost 450 entries, and it's quite difficult to even find *important* submissions.<BR/><BR/>ECCC seems to be better organized.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133837533313413922005-12-05T20:52:00.000-06:002005-12-05T20:52:00.000-06:00Paul,Is it really so hard to browse the archive ef...Paul,<BR/><BR/>Is it really so hard to browse the archive effectively? I rarely read the Computational Complexity section precisely because complexity theorists usually use ECCC instead, not because of the relatively small number of people claiming to have resolved P vs. NP.<BR/><BR/>I find the math section (more precisely, the very nice front at ucdavis) to be a great way of tracking the progress in various fields, and I wish that the same thing existed for CS theory.<BR/><BR/>But in general, weeding out the trolls takes less than a few seconds. Here are the last week's worth of posts to cs.CC on the arxiv:<BR/><BR/>Title: Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity<BR/>Authors: Joel Friedman<BR/><BR/>Title: Phase transition in the assignment problem for random matrices<BR/>Authors: J. G. Esteve, F. Falceto<BR/><BR/>Title: Proving that P is not equal to NP and that P is not equal to the intersection of NP and co-NP<BR/>Authors: R. A. Cohen<BR/><BR/>Title: Quantum Direct Product Theorems for Symmetric Functions and Time-Space Tradeoffs<BR/>Authors: Andris Ambainis (U Waterloo), Robert Spalek (CWI), Ronald de Wolf (CWI)<BR/><BR/>Title: Every sequence is compressible to a random one<BR/>Authors: David Doty<BR/><BR/>Just looking at the titles/authors you can essentially determine whether the papers are actual mathematics. It's not because Cohen's paper is on P vs. NP, it's because the title is akin to "Proving that Red is not Blue, and also that Red and Yellow do not make Green."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133828370077541882005-12-05T18:19:00.000-06:002005-12-05T18:19:00.000-06:00Crypto has the eprint archives (http://eprint.iacr...Crypto has the eprint archives (http://eprint.iacr.org), and it's interesting to look at the growth in the number of papers posted per year. I think it's fair to say also that the average quality of posted papers has declined as the volume has gone up...<BR/><BR/>(I'm not making any recommendations either way, just making an observation)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133823292835537282005-12-05T16:54:00.000-06:002005-12-05T16:54:00.000-06:00Dear Self-Effacing Elitist: what is your problem? ...Dear Self-Effacing Elitist: what is your problem? No one is forcing you to look at all the ECCC submissions. Can't people post what they want and then you can look at what you want? Or do you want ECCC to only post "important" results so that you don't have to figure out yourself what is interesting to you?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133821593568855302005-12-05T16:26:00.000-06:002005-12-05T16:26:00.000-06:00There may be 100 or so submissions to Complexity. ...<I><BR/>There may be 100 or so submissions to Complexity. Do we really want to encourage all of these to be posted on ECCC? </I><BR/><BR/>I would think that any paper that is deemed good enough to be submitted to Complexity would be good enough to be sent to ECCC. The authors may choose to not send it to ECCC for a variety of reasons but that is another issue.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133820603805551092005-12-05T16:10:00.000-06:002005-12-05T16:10:00.000-06:00I'll defend my initial comment as not being elitis...I'll defend my initial comment as not being elitist: First, I was not suggesting to <EM>prevent</EM> anyone from posting to ECCC (minimal selection criteria already exist); I was merely questioning the wisdom of <EM>encouraging</EM> more papers (especially sub-par papers) being posted to ECCC. Second, I follow my own advice: none of my papers are currently posted on ECCC, in part because I can recognize the relative value of my own results (and understand that, while research is a continuum, etc., none of my results are interesting enough to "merit" being posted at ECCC). <BR/><BR/>There may be 100 or so submissions to Complexity. Do we really want to encourage all of these to be posted on ECCC?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133817549966145992005-12-05T15:19:00.000-06:002005-12-05T15:19:00.000-06:00The key for ECCC is that a paper pass a basic test...The key for ECCC is that a paper pass a basic test for coherence and relevance to computational complexity that is enforced by the ECCC submission approval process. <BR/><BR/>CoRR on the LANL arxiv has no such test. Furthermore, the lack of ability to link comments on the arxiv means that there is a great deal of chaff published there under the subject of computational complexity that has no chance of being threshed out.<BR/><BR/>For example, in the last few weeks there are two contradictory submissions claiming<BR/><A HREF="http://arxiv.org/pdf/cs.CC/0511071" REL="nofollow"> P=NP</A> and<BR/><A HREF="http://arxiv.org/pdf/cs.CC/0511085" REL="nofollow"> P != NP</A> that show up alongside the other papers and will never be weeded out. The rate of submissions of this quality on CoRR makes me loath to waste my time looking at it. ECCC always is worth looking at.<BR/><BR/>Paul BeameAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133815956803865912005-12-05T14:52:00.000-06:002005-12-05T14:52:00.000-06:00The previous poster seems prettyelitist. Research ...The previous poster seems pretty<BR/>elitist. Research is a continuum<BR/>and results build upon each other.<BR/>We have conferences, journals etc<BR/>that already impose "interest" level<BR/>thresholds. I don't think we need<BR/>that for electronic distribution<BR/>services. It defeats the amazing <BR/>power of the web to make information <BR/>available and that of search tools <BR/>to make it manageable.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133813452440467992005-12-05T14:10:00.000-06:002005-12-05T14:10:00.000-06:00Why encourage people to post their results on ECCC...Why encourage people to post their results on ECCC? Do you really want that many papers to appear there?<BR/><BR/>I have this quaint notion that ECCC should be reserved for results of sufficient interest to be disseminated quickly. Not all results, even publishable ones, fall into this category.Anonymousnoreply@blogger.com