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,
• 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.
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-084 | 21st May 2015
Or Ordentlich, Ofer Shayevitz, Omri Weinstein

#### Dictatorship is the Most Informative Balanced Function at the Extremes

Suppose $X$ is a uniformly distributed $n$-dimensional binary vector and $Y$ is obtained by passing $X$ through a binary symmetric channel with crossover probability $\alpha$. A recent conjecture by Courtade and Kumar postulates that $I(f(X);Y)\leq 1-h(\alpha)$ for any Boolean function $f$. In this paper, we prove the conjecture for all ... more >>>

TR15-083 | 14th May 2015
Omri Weinstein, David Woodruff

We study $k$-party set disjointness in the simultaneous message-passing model, and show that even if each element $i\in[n]$ is guaranteed to either belong to all $k$ parties or to at most $O(1)$ parties in expectation (and to at most $O(\log n)$ parties with high probability), then $\Omega(n \min(\log 1/\delta, \log ... more >>> TR15-082 | 13th May 2015 Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright #### Beating the random assignment on constraint satisfaction problems of bounded degree We show that for any odd$k$and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a$\frac{1}{2} + \Omega(1/\sqrt{D})$fraction of constraints, where$D\$ is a bound on the number of constraints that each variable occurs in. ... more >>>

-> Older reports

ISSN 1433-8092 | Imprint