What we do and why

The Electronic Colloquium on Computational Complexity is a new forum for the rapid and widespread interchange of ideas, techniques, and research in computational complexity. The purpose of this Colloquium is to use electronic media for scientific communication and discussions in the computational complexity community. The Electronic Colloquium on Computational Complexity (ECCC) welcomes papers, short notes and surveys with

• relevance to the theory of computation,
• clear mathematical profile and
• strictly mathematical format.

Central topics

• models of computation and their complexity,
• trade-off results,
• complexity bounds (with the emphasis on lower bounds).
  Specific areas including complexity issues are
  • combinatorics,
  • communication complexity,
  • cryptography,
  • combinatorial optimization,
  • complexity of learning algorithms,
  • logic.

More reading

Here are some papers on the idea and concept of electronic colloquia and ECCC.

• Christoph Meinel, Volker Klotz
  "The first 10 years of the ECCC digital library"
  Communications of the ACM - CACM, vol. 49, no. 1, pp. 131-134, 2006.
• Jochen Bern, Christoph Meinel, Harald Sack
  "Electronic colloquia: idea and practice"
  ACM Special Interest Group for Design of Communication - SIGDOC, pp. 113-119, 1998.
• Jochen Bern, Carsten Damm, Christoph Meinel "The Electronic Colloquium on Computational Complexity (ECCC): A Digital Library in Use"
  European Conference on Digital Libraries - ECDL, pp. 405-421, 1997.

In 2011 we had a total count of 174 published reports on ECCC. The collection of all the reports from 2011 is now available on DVD. You can order the archive (and also the archive DVDs from earlier years) at the local office. Please email to eccc@eccc.hpi-web.de for ordering.

The collection of all reports published on ECCC in 2010 is now available on DVD. You can order the archive (and also the archive DVDs from earlier years) at the local office.
Please email to eccc@eccc.hpi-web.de for ordering.

With the extension of our scientific board and the implementation of the improved screening mechanism incorporating topics of interest already in the submission process, the ECCC can now provide a clarified Call for Papers.
Please keep in mind, that the ECCC focusses on complexity issues rather than on general algorithmic topics. If you plan to submit, please verify that your work matches the scope of interest defined in the CfP.

A propositional proof system is \emph{weakly automatizable} if there
is a polynomial time algorithm which separates satisfiable formulas
from formulas which have a short refutation in the system, with
respect to a given length bound. We show that if the resolution
proof system is weakly automatizable, ... more >>>

We consider arithmetic formulas consisting of alternating layers of addition $(+)$ and multiplication $(\times)$ gates such that the fanin of all the gates in any fixed layer is the same. Such a formula $\Phi$ which additionally has the property that its formal/syntactic degree is at most twice the (total) degree ... more >>>

We study lower bounds for testing membership in families of linear/affine-invariant Boolean functions over the hypercube. A family of functions $P\subseteq \{\{0,1\}^n \rightarrow \{0,1\}\}$ is linear/affine invariant if for any $f\in P$, it is the case that $f\circ L\in P$ for any linear/affine transformation $L$ of the domain. Motivated by ... more >>>