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
- relevance to computational complexity
- clear mathematical profile and
- 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.
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)
- 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.
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:
David Mix Barrington
Peter Bro Miltersen
Dieter van Melkebeek
Editor in Chief: Oded Goldreich