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 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.

Latest News
7th December 2009 10:22

Improved Screening Mechanism

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.

6th October 2009 22:32

Extending the Scientific Board

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.

27th July 2009 13:58

Relaunching ECCC

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.


-> Older news
Latest Reports
TR10-016 | 22nd December 2009
Alexander Fanghänel, Sascha Geulen, Martin Hoefer, Berthold Vöcking

Online Capacity Maximization in Wireless Networks

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 >>>

TR10-015 | 8th February 2010
Maurice Jansen, Youming Qiao, Jayalal Sarma

Deterministic Black-Box Identity Testing $\pi$-Ordered Algebraic Branching Programs

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 >>>

TR10-014 | 2nd February 2010
Daniele Micciancio, Panagiotis Voulgaris

A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations

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 >>>

-> Older reports


ISSN 1433-8092 | Imprint