ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



ABOUT THE COLLOQUIUM > CALL FOR PAPERS:
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
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