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
TR15-030 | 6th March 2015
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

#### ${\mathrm{AC}^{0} \circ \mathrm{MOD}_2}$ lower bounds for the Boolean Inner Product

$\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuits are $\mathrm{AC}^{0}$ circuits augmented with a layer of parity gates just above the input layer. We study the $\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuit lower bound for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have ... more >>>

TR15-029 | 18th February 2015
Stanislav Zak

#### Inherent logic and complexity

Abstract. The old intuitive question "what does the machine think" at
different stages of its computation is examined. Our paper is based on
the formal de nitions and results which are collected in the branching
program theory around the intuitive question "what does the program
know about the contents of ... more >>>

TR15-028 | 27th February 2015
Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Lauriere, Jérémie Roland

#### Relative Discrepancy does not separate Information and Communication Complexity

Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Recently, Ganor et al. provided such a separation in the distributional setting for a specific input distribution ?. We show that ... more >>>

-> Older reports

ISSN 1433-8092 | Imprint