WEBSITE > HOME:

#### 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,
• 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.

Here are some papers on the idea and concept of electronic colloquia and ECCC.
7th April 2014 13:36

#### ECCC Archive DVD 2013

191 reports have been published on ECCC in 2013. The collection of all these reports is now available on DVD. You can order the archive (and also the archive DVDs from earlier years) at the local office. Please email < href="mailto:eccc@eccc.hpi-web.de">eccc@eccc.hpi-web.de for ordering.

4th March 2013 09:03

#### ECCC Archive DVD 2012

In 2012 we had a total count of 186 published reports on ECCC. The collection of all the reports from 2012 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.

6th March 2012 12:04

#### ECCC Archive DVD 2011

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.

-> Older news
TR14-120 | 16th September 2014
Olaf Beyersdorff, Leroy Chew, Mikolas Janota

#### Proof Complexity of Resolution-based QBF Calculi

Proof systems for quantified Boolean formulas (QBFs) provide a theoretical underpinning for the performance of important
QBF solvers. However, the proof complexity of these proof systems is currently not well understood and in particular
lower bound techniques are missing. In this paper we exhibit a new and elegant proof technique ... more >>>

TR14-119 | 15th September 2014
Mark Braverman, Jieming Mao

#### Simulating Noisy Channel Interaction

We show that $T$ rounds of interaction over the binary symmetric channel $BSC_{1/2-\epsilon}$ with feedback can be simulated with $O(\epsilon^2 T)$ rounds of interaction over a noiseless channel. We also introduce a more general "energy cost'' model of interaction over a noisy channel. We show energy cost to be equivalent ... more >>>

TR14-118 | 9th September 2014
Albert Atserias, Massimo Lauria, Jakob Nordström

#### Narrow Proofs May Be Maximally Long

We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size n^Omega(w). This shows that the simple counting argument that any formula refutable in width w must have a proof in size n^O(w) is essentially tight. ... more >>>

-> Older reports

ISSN 1433-8092 | Imprint