Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] ECCC

Expand Messages
  • Lance
    One of the main topics of discussion at CCC last week centered around the problems with the Electronic Colloquium on Computational Complexity now 15 years old
    Message 1 of 1 , Jul 21, 2009
    • 0 Attachment
      One of the main topics of discussion at CCC last week centered around the problems with the Electronic Colloquium on Computational Complexity now 15 years old and showing its age.

      In 1994, ECCC truly innovated the way we discover research. ECCC has a large board of editors that in theory quickly accept submissions that reach a minimum quality level in computational complexity. Once ECCC hit critical mass it became the must check place to see the latest results in complexity. I first heard about Omer Reingold's L=SL result from its ECCC post

      Roughly here is how ECCC works: Once submitted, anyone on the ECCC scientific board can look at the paper and either accept or reject through a clunky email interface. Once accepted the paper appears nearly immediately. Papers by board members are automatically accepted. Papers not acted upon after two months are automatically rejected. A weekly email goes out to the board listing new and about-to-expire papers. 

      Most papers are either accepted immediately if an editor is interested in it, or right before it expires. But often papers fall through the cracks, or the email doesn't get sent and papers time out. Recently many reasonable papers did time out which led to the discussions at the Complexity Conference. Also the site hasn't been updated much and is sometimes down or not working properly.

      The main alternative to ECCC is the Computational Complexity section of the Computing Research Repository, now part of the ArXiv maintained by the Cornell University libraries and thus usually more more reliable than ECCC.

      I subscribe to the RSS feeds for complexity papers on both ECCC and the CoRR. CoRR has a policy of accepting all papers in scope, including various P v NP "proofs", and most active complexity theorists self-select ECCC so only a few CoRR papers are interesting to me.

      Scott Aaronson led a discussion at the CCC business meeting on suggestions on what to do with ECCC, not that the Complexity conference has any active role in ECCC. There were many thoughts including changing some of the policies by perhaps assigning papers to editors or have acceptance instead of rejection as a default, or have ECCC as just an overlay over CoRR to increase reliability. Maybe we just need to find a way to make sure more submissions get processed.

      As the number of researchers and papers in complexity has increased, we have come to rely on systems like ECCC to let us learn the latest important results without having to wade through the chaff. When these systems fail us, even in little ways, we feel lost. But we can't fault the people who run ECCC, they have served us well for a decade and a half with little remuneration. But we need something or we will have to go back to the old ways of learning about good papers from conferences and journals.

      Posted By Lance to Computational Complexity at 7/21/2009 11:15:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.