Electronic Colloquium on Computational Complexity
Login | Register | Classic Style

The Electronic Colloquium on Computational Complexity is a forum for the rapid and widespread interchange of ideas, techniques, and research in computational complexity. The Electronic Colloquium on Computational Complexity (ECCC) welcomes papers, short notes and surveys with
  1. relevance to computational complexity
  2. clear mathematical profile and
  3. strictly mathematical format.
To be posted on ECCC, a submission should meet the following criteria
  • be in the scope (see below)
  • look somewhat new and interesting
  • contain all proofs
  • be in a readable form.
There are no submission deadlines: papers are stored in the archive one by one constantly.

The scope

Typical topics covered by ECCC include
  • Algebraic and arithmetic complexity
  • Average case complexity
  • Circuit complexity
  • Coding theory (complexity aspects only)
  • Communication complexity
  • Cryptography (complexity aspects only)
  • Data structure lower bounds
  • Game theory (complexity aspects only)
  • Inapproximability
  • Interactive and probabilistic proof systems
  • Kolmogorov complexity
  • Learning (complexity aspects only)
  • Proof complexity
  • Property testing (complexity aspects only)
  • Pseudorandomness and derandomization
  • Quantum computation (complexity aspects only)
  • Structural complexity
This is not meant as an exhaustive list; studies in other areas of computer science and mathematics dealing with computational complexity or developing techniques relevant to it are welcomed too.

Indeed, the main focus of computational complexity and ECCC is on understanding the limits of what algorithms can do. Thus, typically, algorithmic improvements are not in scope of ECCC, except in cases where either the improved complexity bounds are closely related to a conjectured lower bound or the techniques are of natural interest to complexity-theoretic studies.

Note that while many areas in computer science (e.g., cryptography) are closely related to complexity theory, this does not mean that every work in these areas is in the scope of ECCC. In such cases, determining whether a submission is in scope depends on how dominant the complexity-theoretic aspects are in the submission.

Submissions making incredible claims, including but not limited to resolutions of the P vs NP problem, may be rejected without further consideration.

Other features

Publication in ECCC provides the innovative feature of an ongoing public scientific discussion. Corrections, improvements, remarks etc. concerning an existing ECCC Report may be submitted by either author or reader and are kept with the original submission thus being accessible to all.

Submission to ECCC does not prevent future submission to any conference or journal: the submissions which appear in the archive have the status of technical reports.

The scientific board

ECCC activity is supervised by a scientific board. In particular, the board makes sure that ECCC Reports meet the minimal standards described above. The scientific board decides for publication of a submission within two months on the basis of a screening process. Specifically, each submission is screened by the scientific board and a decision whether to post it as a report is reached within two months. (All board members are notified of all pending submissions once in two weeks and screen submissions at their own choice.) A submission may be rejected due to a lack of interest, the impression that it is out of scope or unlikely to be correct, or that it failed to provide sufficient justification.

The scientific board of ECCC consists of:

Scott Aaronson
Miklos Ajtai
Eric Allender
Noga Alon
Sanjeev Arora
Boaz Barak
David Mix Barrington
Paul Beame
Richard Beigel
Eli Ben-Sasson
Harry Buhrman
Constantinos Daskalakis
Irit Dinur
Anna Gal
Oded Goldreich
Venkatesan Guruswami
Johan Hastad
Yuval Ishai
Stasys Jukna
Valentine Kabanets
Marek Karpinski
Subhash Khot
Nathan Linial
Kurt Mehlhorn
Peter Bro Miltersen
Ryan O'Donnell
Pavel Pudlak
Anup Rao
Ran Raz
Alexander Razborov
Oded Regev
Omer Reingold
RĂ¼diger Reischuk
Michael Saks
Rocco Servedio
Ronen Shaltiel
Peter Shor
Amir Shpilka
Madhu Sudan
Mario Szegedy
Luca Trevisan
Chris Umans
Salil Vadhan
Dieter van Melkebeek
Emanuele Viola
Avi Wigderson

Editor in Chief: Oded Goldreich

ISSN 1433-8092 | Imprint