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-321 | 19th November 2026
Tal Herman

The Communication Complexity of Verifying Distribution Properties

Suppose an untrusted powerful data analyst collected many samples from an unknown distribution, and claims that the distribution satisfies some property. For example, that it is close to uniform, or has large support. Can they provide a convincing proof to this effect? If so, what is the complexity of certifying ... more >>>


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



Next next


ISSN 1433-8092 | Imprint