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.


-> Older news


Latest Report Titles
Latest Reports
TR25-116 | 28th July 2025
Dmitry Itsykson, Alexander Knop

Supercritical Tradeoff Between Size and Depth for Resolution over Parities

Alekseev and Itsykson (STOC 2025) proved the existence of an unsatisfiable CNF formula such that any resolution over parities (Res($\oplus$)) refutation must either have exponential size (in the formula size) or superlinear depth (in the number of variables). In this paper, we extend this result by constructing a formula with ... more >>>


TR25-108 | 1st August 2025
Divesh Aggarwal, Pranjal Dutta, Saswata Mukherjee, Satyajeet Nagargoje, Maciej Obremski

Efficient randomized strong $2$-source non-malleable extractor for any linear min-entropy.

Randomness is a fundamental requirement in cryptographic systems, enabling secure encryption, commitments, and zero-knowledge proofs. However, real-world randomness sources often suffer from weaknesses that adversaries can exploit, leading to significant security vulnerabilities. While deterministic randomness extraction from a single min-entropy source is impossible, two-source extractors provide a robust solution by ... more >>>


TR25-107 | 1st August 2025
Justin Oh, Ronen Shaltiel

Extractors for Samplable Distributions from the Two-Source Extractor Recipe

Trevisan and Vadhan [TV00] first constructed seedless extractors for distributions samplable by poly-size circuits under the very strong complexity theoretic hardness assumption that $E=DTIME(2^{O(n)})$ is hard for exponential size circuits with oracle access to $\Sigma_6^{P}$. Their construction works when the distribution has large min-entropy $k=(1-\gamma) \cdot n$, for small constant ... more >>>


-> Older reports


ISSN 1433-8092 | Imprint