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.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.
Two-way codes use communication in both directions to convey a message from a sender to a receiver over a noisy channel. In a beautiful work, [GKZ22] proved that for binary channels with adversarial erasures, interaction strictly outperforms one-way communication: they constructed a two-way code with erasure resilience approaching 3/5, surpassing ... more >>>
It is well-known that if $\mathrm{P} = \mathrm{NP}$, then the seemingly larger class $\mathrm{PH}$ also collapses to $\mathrm{P}$; hence, we may base the hardness of $\mathrm{NP}$ on that of $\mathrm{PH}$, despite the widespread belief that $\mathrm{PH} \not\subseteq \mathrm{NP}$. Although well established in the decision problem setting, few such “conditional collapse ... more >>>
Rossman, Servedio, and Tan proved that the polynomial hierarchy is infinite relative to a random oracle. This paper strengthens this celebrated result by considering strong separations, witnessed by immune languages.
The main result of the paper shows that with respect to a random oracle the levels of the polynomial ... more >>>