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. ECCC welcomes papers, short notes, and surveys, with
  • relevance to computational complexity,
  • clear mathematical profile, and
  • alignment with the scholarly norms.

Submissions claiming to resolve a grand challenge, such as the P vs. NP problem, may be rejected without further consideration.

Submissions containing an essential part that seems to be generated by AI tools and/or are written in a way that humans will find hard to understand, may be rejected regardless of their merits. ECCC is intended for communication among humans.

For more details see the Call for Papers.


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
TR26-325 | 21st November 2026
Marshall Ball, Peter Crawford-Kahrl, Vladimir Podolskii, Morgan Prior

On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous Messages

Multiparty Private Simultaneous Messages (PSM), also known as Decomposable Randomized Encoding (DRE) or information-theoretic garbling, is a model for non-interactive secure computation. Each party encodes its input using shared randomness and sends a message to an evaluator who does not know that randomness. The evaluator must recover the function output ... more >>>


TR26-324 | 20th November 2026
Emanuele Viola

A power saving for pointer chasing

Three-player number-on-forehead pointer chasing has communication complexity $\le n^{1-c}$. A bound $n/\log^{c}n$ was known since the 90's.

more >>>

TR26-323 | 20th November 2026
William Hoza

NL = UL

We present an explicit weight assignment generator that uses a seed of length $O(\log(wn))$ to assign a polynomially-bounded integer weight to each vertex of any simple width-$w$ length-$n$ layered digraph. For each such digraph, there is at least one seed such that the weight function is min-isolating, i.e., the minimum-weight ... more >>>


-> Older reports


ISSN 1433-8092 | Imprint