Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-FeedNext next

TR26-320 | 16th November 2026
Klim Efremenko, Gillat Kol, Sergey Komech, Raghuvansh Saxena, Zhijun Zhang

Binary Two-Way Codes with Optimal Erasure Resilience

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 >>>


TR26-319 | 5th November 2026
Surendra Ghentiyala, Oliver Korten, Toniann Pitassi

Power and Limitations of TFNP Hierarchies

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 >>>


TR26-318 | 4th October 2026
Gabriel Istrate

Separations with Immunity Relative to a Random Oracle in Computational Complexity

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 >>>



Next next


ISSN 1433-8092 | Imprint