Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-151 | 17th October 2025 08:46

Constant Rate Codes for Adaptive Broadcasts Do Not Exist

RSS-Feed




TR25-151
Authors: Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
Publication: 19th October 2025 21:33
Downloads: 20
Keywords: 


Abstract:

Can the $n$-party broadcast channel, where any symbol sent by one party is received by all, be made resilient to noise with low overhead? Namely, is it possible to construct interactive error-correcting codes that convert any protocol designed for the noiseless broadcast channel into one that works over the noisy broadcast channel and is not much longer than the original protocol?

[EKS18, STOC 2018] showed that such interactive codes with constant multiplicative overhead are possible under the assumption that the noiseless protocol being simulated is non-adaptive, meaning that it is restricted to have a pre-determined order of turns. Their noise resilient simulating protocols, however, require adaptivity, where each party can decide whether or not to broadcast given all the information available to them, including their input and received transcript. The question of whether such a simulation is possible for general, potentially adaptive, noiseless protocols was left open.

We resolve this question negatively, proving that any interactive code that converts adaptive noiseless broadcast protocols into adaptive broadcast protocols resilient to stochastic errors must incur a multiplicative overhead of $\Omega(\log n / \log \log n)$, which is nearly tight.



ISSN 1433-8092 | Imprint