Monday, December 05, 2005

The Day After

Many of you submitted papers to the Complexity conference by yesterday's deadline, now you should let the world see them. Submit your papers to an archive center like CoRR and/or ECCC. It's never too late to submit your STOC submissions as well.

Talking about the ECCC, Xi Chen and Xiaotie Deng have posted a new paper that apparently shows that 2-player Nash Equilibrium has the same complexity as finding fixed points (PPAD-complete), extending the 4-player result I mentioned in October. A bit surprising, most of us thought that 2-player Nash would be easier to solve.


  1. Why encourage people to post their results on ECCC? Do you really want that many papers to appear there?

    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.

  2. The previous poster seems pretty
    elitist. Research is a continuum
    and results build upon each other.
    We have conferences, journals etc
    that already impose "interest" level
    thresholds. I don't think we need
    that for electronic distribution
    services. It defeats the amazing
    power of the web to make information
    available and that of search tools
    to make it manageable.

  3. 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.

    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.

    For example, in the last few weeks there are two contradictory submissions claiming
    P=NP and
    P != NP 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.

    Paul Beame

  4. I'll defend my initial comment as not being elitist: First, I was not suggesting to prevent anyone from posting to ECCC (minimal selection criteria already exist); I was merely questioning the wisdom of encouraging 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).

    There may be 100 or so submissions to Complexity. Do we really want to encourage all of these to be posted on ECCC?


  5. There may be 100 or so submissions to Complexity. Do we really want to encourage all of these to be posted on ECCC?

    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.

  6. 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?

  7. Crypto has the eprint archives (, 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...

    (I'm not making any recommendations either way, just making an observation)

  8. Paul,

    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.

    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.

    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:

    Title: Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity
    Authors: Joel Friedman

    Title: Phase transition in the assignment problem for random matrices
    Authors: J. G. Esteve, F. Falceto

    Title: Proving that P is not equal to NP and that P is not equal to the intersection of NP and co-NP
    Authors: R. A. Cohen

    Title: Quantum Direct Product Theorems for Symmetric Functions and Time-Space Tradeoffs
    Authors: Andris Ambainis (U Waterloo), Robert Spalek (CWI), Ronald de Wolf (CWI)

    Title: Every sequence is compressible to a random one
    Authors: David Doty

    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."

  9. Re: Jonathan Katz's comment

    Crypto has eprint, (, 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.

    This year, there are almost 450 entries, and it's quite difficult to even find *important* submissions.

    ECCC seems to be better organized.

  10. 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.