Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



WEBSITE > HOME:
About the ECCC

What we do and why

The Electronic Colloquium on Computational Complexity (ECCC) was established in 1994 as a forum and repository for the rapid and widespread interchange of ideas, techniques, and research in computational complexity. Posting on the ECCC has the status of a technical report. The Electronic Colloquium on Computational Complexity 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.
  • complexity bounds and trade-offs (with the emphasis on lower bounds).
  • complexity theoretic aspects of specific areas including coding theory, combinatorics, cryptography, game theory, logic, machine learning, optimization, property testing, and quantum computation.
For more details see the Call for Papers.

More reading

Here are some papers on the idea and concept of electronic colloquia and ECCC.

Latest News
9th April 2023 12:21

Service Interruption

In the last few days, a Denial of Service attack was launched on universities in Israel, leading the administrators of the Israel Academic network to block access to it from the global internet. Consequently, websites such as ECCC have been accessible only from within the Israeli and European academic networks.

It seems that this blocking was just removed, and we hope it will not be put back in the future.

Needless to say, deciding on such blocking is not in our control, but we do apologize for this disruption of service.


5th January 2017 18:30

ECCC relocated to Weizmann Institute

The ECCC has just relocated at the Weizmann Institute of Science. The previous locations were first at the University of Trier (1994-2004), and then at the Hasso Plattner Institute (2004-2016).

Our new URL is eccc.weizmann.ac.il, and the previous URL (eccc.hpi-web.de) is supposed to redirect to the new location. All hyperlinks to reports are still functional after the transition.

Our first priority at the next couple of weeks is to verify that the transition has been performed smoothly and that all existing features work as they used to. (Later on and as circumstances permit, we shall perform various minor improvements, which were on our TODO list for a while.)

Please inform Amir Gonen (amir.gonen@weizmann.ac.il), while CCing Oded Goldreich (oded.goldreich@weizmann.ac.il), as soon as you discover anything that does not function as it used to.

At this point, I would like to thank Christoph Meinel, who has been one of the founders of ECCC and served as its chief editor and head of its local office for 23 years. Special thanks also to Christian Willems, who has provided the technical support for the operation of ECCC for the last few years and has supervised the current transition from the sending side. (I am aware that others deserves much credits as well, but regret that I cannot provide the relevant details at this time. Providing a full account of the history of the establishing of ECCC and its operation since 1994, in the form of a "History of ECCC" page, is on our TODO list.)

Lastly, many thanks to Amir Gonen for performing the transition on the receiving side and for agreeing to undertake the operation from this point on.

Oded Goldreich


23rd December 2016 12:53

ECCC moves to Weizmann Institute

After 23 years of running the ECCC, first at the University of Trier, then at the Hasso Plattner Institute, the ECCC will find a new home at the Weizmann Institute.

This smooth transition will happen with the beginning of 2017. We will keep you informed upfront.


-> Older news
Latest Report Titles
Latest Reports
TR25-014 | 18th February 2025
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh Saxena

Information Dissemination via Broadcasts in the Presence of Adversarial Noise

We initiate the study of error correcting codes over the multi-party adversarial broadcast channel. Specifically, we consider the classic information dissemination problem where $n$ parties, each holding an input bit, wish to know each other's input. For this, they communicate in rounds, where, in each round, one designated party sends ... more >>>


TR25-013 | 18th February 2025
Raghuvansh Saxena, Yael Tauman Kalai

Polynomial Size, Short-Circuit Resilient Circuits for NC

We show how to convert any circuit of poly-logarithmic depth and polynomial size into a functionally equivalent circuit of polynomial size (and polynomial depth) that is resilient to adversarial short-circuit errors. Specifically, the resulting circuit computes the same function even if up to $\epsilon d$ gates on every root-to-leaf path ... more >>>


TR25-012 | 17th February 2025
Dean Doron, Ori Fridman

Bit-Fixing Extractors for Almost-Logarithmic Entropy

An oblivious bit-fixing source is a distribution over $\{0,1\}^n$, where $k$ bits are uniform and independent and the rest $n-k$ are fixed a priori to some constant value. Extracting (close to) true randomness from an oblivious bit-fixing source has been studied since the 1980s, with applications in cryptography and complexity ... more >>>


-> Older reports


ISSN 1433-8092 | Imprint