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



WEBSITE > HOME:
About the ECCC

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.
Latest News
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
Latest Reports
TR16-114 | 30th July 2016
Gil Cohen

Two-Source Extractors for Quasi-Logarithmic Min-Entropy and Improved Privacy Amplification Protocols

This paper offers the following contributions:

* We construct a two-source extractor for quasi-logarithmic min-entropy. That is, an extractor for two independent $n$-bit sources with min-entropy $\widetilde{O}(\log{n})$. Our construction is optimal up to $\mathrm{poly}(\log\log{n})$ factors and improves upon a recent result by Ben-Aroya, Doron, and Ta-Shma (ECCC'16) that can handle ... more >>>


TR16-113 | 22nd July 2016
Gillat Kol, Ran Raz, Avishay Tal

Time-Space Hardness of Learning Sparse Parities

We define a concept class ${\cal F}$ to be time-space hard (or memory-samples hard) if any learning algorithm for ${\cal F}$ requires either a memory of size super-linear in $n$ or a number of samples super-polynomial in $n$, where $n$ is the length of one sample.

A recent work shows ... more >>>


TR16-112 | 18th July 2016
Mohammad T. Hajiaghayi, Amey Bhangale, Rajiv Gandhi, Rohit Khandekar, Guy Kortsarz

Bicovering: Covering edges with two small subsets of vertices

We study the following basic problem called Bi-Covering. Given a graph $G(V,E)$, find two (not necessarily disjoint) sets $A\subseteq V$ and $B\subseteq V$ such that $A\cup B = V$ and that every edge $e$ belongs to either the graph induced by $A$ or to the graph induced by $B$. The ... more >>>


-> Older reports


ISSN 1433-8092 | Imprint