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
**no submission deadlines**: papers are stored in the archive one by one constantly.
### The scope

Typical topics covered by ECCC include
### 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.
### 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.

- relevance to computational complexity
- clear mathematical profile and
- strictly mathematical format.

- be in the scope (see below)
- look somewhat new and interesting
- contain all proofs
- be in a readable form.

- 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

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.

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