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-099 | 17th July 2025
Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, Amir Yehudayoff

The Algebraic Cost of a Boolean Sum

It is a well-known fact that the permanent polynomial is complete for the complexity class VNP, and it is largely suspected that the determinant does not share this property, despite its similar expression.
We study the question of why the VNP-completeness proof of the permanent fails for the determinant.
We ... more >>>


TR25-098 | 17th July 2025
Prerona Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, Amit Sinhababu

IPS Lower Bounds for Formulas and Sum of ROABPs

We give new lower bounds for the fragments of the Ideal Proof System (IPS) introduced by Grochow and Pitassi (JACM 2018). The Ideal Proof System is a central topic in algebraic proof complexity developed in the context of Nullstellensatz refutation (Beame, Impagliazzo, Krajicek, Pitassi, Pudlak, FOCS 1994) and simulates Extended ... more >>>


TR25-097 | 16th July 2025
Hadar Strauss

On the Limits of Computationally Sound IPPs in the Isolated Model

Interactive proofs of proximity (IPPs) are a relaxation of interactive proofs, analogous to property testing, in which soundness is required to hold only for inputs that are far from the property being verified. In such proof systems, the verifier has oracle access to the input, and it engages in two ... more >>>


-> Older reports


ISSN 1433-8092 | Imprint