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.

In this paper we demonstrate a close connection between UniqueGames and MultiCut. % In MultiCut, one is given a ``network graph'' and a ``demand graph'' on the same vertex set and the goal is to remove as few edges from the network graph as possible such that every two vertices ... more >>>

In this paper we will be concerned with a large class of packing and covering problems which includes Vertex Cover and Independent Set. Typically, for NP-hard problems among them, one can write an LP relaxation and then round the solution. For instance, for Vertex Cover, one can obtain a 2-approximation ... more >>>

Which computational intractability assumptions are inherent to cryptography? We present a broad framework to pose and investigate this question. We first aim to understand the “cryptographic complexity” of various tasks, independent of any computational assumptions. In our framework the cryptographic tasks are modeled as multi- party computation functionalities. We consider ... more >>>