What we do and why

The Electronic Colloquium on Computational Complexity is a forum for the rapid and widespread interchange of ideas, techniques, and research in computational complexity. The purpose of this forum 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 computational complexity
• clear mathematical profile and
• strictly mathematical format.

The scope

Typical topics covered by ECCC include Algebraic and arithmetic complexity, Average case complexity, Circuit complexity, Communication complexity, Data structure lower bounds, Inapproximability, Interactive and probabilistic proof systems, Kolmogorov complexity, Proof complexity, Pseudorandomness and derandomization, and Structural complexity. This is not meant as an exhaustive list; studies in other areas of computer science and mathematics dealing with computational complexity or developing techniques relevant to it are welcomed too. In particlar, papers addressing complexity aspects of Coding theory, Cryptography, Game theory, Learning, Property testing, and Quantum computation are considered in the scope of ECCC.

Indeed, the main focus of computational complexity and ECCC is on understanding the limits of what algorithms can do. Thus, typically, algorithmic improvements are not in scope of ECCC, except in cases where either the improved complexity bounds are closely related to a conjectured lower bound or the techniques are of natural interest to complexity-theoretic studies. Likewise, while many areas in computer science (e.g., cryptography) are closely related to complexity theory, this does not mean that every work in these areas is in the scope of ECCC.

In order to address the increasing number of submissions from a growing variety of topics and with the aim of decreasing the response time of ECCC in general we are currently extending the scientific board.

After 15 years of successful operation the time for renewal has come. Of course you can see the new layout, but also the underlying software solution has been completely re-implemented using modern web technology.

The new system will not only allow easier access for readers of the reports but also provides more convenient paper submission and reviewing processes.

Additional features include:

• Reports and submissions will be in Portable Document Format (.pdf)
• User account for the website enabling you to keep track of all your submissions
• More RSS feeds
• Several features for the local office and reviewers to increase response time and efficiency
• ... and many more.

The classic ECCC layout style has been preserved and can be activated by clicking on classic style.

We construct a small set of explicit linear transformations mapping $R^n$ to $R^{O(\log n)}$, such that the $L_2$ norm of any vector in $R^n$ is distorted by at most $1\pm o(1)$ in at least a fraction of $1 - o(1)$ of the transformations in the set. Albeit the tradeoff between ... more >>>

We consider weakly-verifiable puzzles which are challenge-response puzzles such that the responder may not be able to verify for itself whether it answered the challenge correctly. We consider $k$-wise direct product of such puzzles, where now the responder has to solve $k$ puzzles chosen independently in parallel. Canetti et al ... more >>>

Motivated by a concrete problem and with the goal of understanding the sense in which the complexity of streaming algorithms is related to the complexity of formal languages, we investigate the problem Dyck(s) of checking matching parentheses, with $s$ different types of parenthesis. We present a one-pass randomized streaming algorithm ... more >>>