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-162 | 28th November 2014
Michael Forbes, Venkatesan Guruswami

#### Dimension Expanders via Rank Condensers

An emerging theory of "linear-algebraic pseudorandomness" aims to understand the linear-algebraic analogs of fundamental Boolean pseudorandom objects where the rank of subspaces plays the role of the size of subsets. In this work, we study and highlight the interrelationships between several such algebraic objects such as subspace designs, dimension ... more >>>

TR14-161 | 27th November 2014
Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari

#### Derandomizing Isolation Lemma for $K_{3,3}$-free and $K_5$-free Bipartite Graphs

The perfect matching problem has a randomized $NC$ algorithm, using the celebrated Isolation Lemma of Mulmuley, Vazirani and Vazirani. The Isolation Lemma states that giving a random weight assignment to the edges of a graph, ensures that it has a unique minimum weight perfect matching, with a good probability. We ... more >>>

TR14-160 | 27th November 2014
Gil Cohen, Igor Shinkar

#### Zero-Fixing Extractors for Sub-Logarithmic Entropy

An $(n,k)$-bit-fixing source is a distribution on $n$ bit strings, that is fixed on $n-k$ of the coordinates, and jointly uniform on the remaining $k$ bits. Explicit constructions of bit-fixing extractors by Gabizon, Raz and Shaltiel [SICOMP 2006] and Rao [CCC 2009], extract $(1-o(1)) \cdot k$ bits for \$k = ... more >>>

-> Older reports

ISSN 1433-8092 | Imprint