The Electronic Colloquium on Computational Complexity (ECCC) is a forum for the rapid and widespread interchange of ideas, techniques, and research in computational complexity. The 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 scope (see below),
• look somewhat new and interesting,
• contain all proofs, and
• be in a readable form.

There are no submission deadlines: papers are stored in the archive one by one constantly.

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 welcome 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 its complexity-theoretic aspects are.

Submissions claiming to resolve a grand challenge, such as the P vs. NP problem, may be rejected without further consideration.

Other features

Publication in ECCC enables the 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 that appear in the archive have the status of technical reports.

The scientific board

ECCC activity is supervised by a scientific board, which makes sure that ECCC Reports meet the minimal standards described above. As soon as a submission arrives, several board members with expertise in its declared area are notified, and once a week all board members are sent the list of pending submissions. Board members may screen a submission at their own discretion, and make the decision whether or not to accept it. An accepted submission is posted as a report immediately. A submission is automatically rejected after two months if no board member accepted it. This may indicate that the submission is not of sufficient interest to the complexity community.

The current scientific board of ECCC consists of:

Scott Aaronson Miklos Ajtai Noga Alon Albert Atserias Boaz Barak David Mix Barrington Paul Beame Richard Beigel Eli Ben-Sasson Harry Buhrman Constantinos Daskalakis Irit Dinur Anna Gal Oded Goldreich Rohit Gurjar Venkatesan Guruswami Prahladh Harsha Johan Håstad Yuval Ishai

Stasys Jukna Valentine Kabanets Marek Karpinski Subhash Khot Swastik Kopparty Michal Koucky Shachar Lovett Meena Mahajan Kurt Mehlhorn Or Meir Raghu Meka Peter Bro Miltersen Jakob Nordström Ryan O'Donnell Toniann Pitassi Pavel Pudlak Anup Rao Ran Raz Alexander Razborov

Oded Regev Omer Reingold Rüdiger Reischuk Rahul Santhanam Shubhangi Saraf Rocco Servedio Ronen Shaltiel Peter Shor Amir Shpilka Madhu Sudan Mario Szegedy Chris Umans Salil Vadhan Dieter van Melkebeek Virginia Vassilevska Williams Thomas Vidick Emanuele Viola Avi Wigderson Ryan Williams

Editor in Chief: Oded Goldreich

---

ISSN 1433-8092 | Imprint