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.

We recently modified the ECCC screening mechanism to meet the demand of fast response times of the scientific board. We ask all authors to choose the primary and secondary topics of their papers carefully as we're using this information to decide which editor should review your paper.

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 study a dynamic version of capacity maximization in the physical model of wireless communication. In our model, requests for connections between pairs of points in Euclidean space of constant dimension $d$ arrive iteratively over time. When a new request arrives, an online algorithm needs to decide ... more >>>

In this paper we study algebraic branching programs (ABPs) with restrictions on the order and the number of reads of variables in the program. Given a permutation $\pi$ of $n$ variables, for a $\pi$-ordered ABP ($\pi$-OABP), for any directed path $p$ from source to sink, a variable can appear at ... more >>>

We give deterministic $2^{O(n)}$-time algorithms to solve all the most important computational problems on point lattices in NP, including the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), and Shortest Independent Vectors Problem (SIVP). This improves the $n^{O(n)}$ running time of the best previously known algorithms for CVP (Kannan, Math. ... more >>>