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-182 | 16th November 2025
Oded Goldreich

Proving the PCP Theorem with 1.5 proof compositions (or yet another PCP construction)

The original proof of the PCP Theorem composes a Reed-Muller-based PCP with itself, and then composes the resulting PCP with a Hadamard-based PCP [Arora, Lund, Motwani, Sudan and Szegedy ({\em JACM}, 1998)].
Hence, that proof applies a (general) proof composition result twice.
(Dinur's alternative proof consists of logarithmically many gap ... more >>>


TR25-181 | 11th November 2025
Bruno Pasqualotto Cavalar, Eli Goldin, Matthew Gray, Taiga Hiroka, Tomoyuki Morimae

On Cryptography and Distribution Verification, with Applications to Quantum Advantage

One of the most fundamental problems in the field of hypothesis testing is the identity testing problem: whether samples from some unknown distribution $\mathcal{G}$ are actually from some explicit distribution $\mathcal{D}$. It is known that when the distribution $\mathcal{D}$ has support $[N]$, the optimal sample complexity for the identity testing ... more >>>


TR25-180 | 13th November 2025
Ryan O'Donnell, Noah Singer

Low-soundness direct-product testers and PCPs from Kaufman--Oppenheim complexes

We study the Kaufman--Oppenheim coset complexes (STOC 2018, Eur. J. Comb. 2023), which have an elementary and strongly explicit description. Answering an open question of Kaufman, Oppenheim, and Weinberger (STOC 2025), we show that they support sparse direct-product testers in the low soundness regime. Our proof relies on the HDX ... more >>>


-> Older reports


ISSN 1433-8092 | Imprint