Skip to main navigation Skip to search Skip to main content

Constant Rate Codes for Adaptive Broadcasts Do Not Exist

  • Klim Efremenko
  • , Gillat Kol
  • , Dmitry Paramonov
  • , Raghuvansh R. Saxena
    • Ben-Gurion University of the Negev
    • Princeton University
    • Tata Institute of Fundamental Research

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    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?[12, 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 Ω(log n/ log log n), which is nearly tight.

    Original languageEnglish
    Title of host publicationProceedings - 2025 IEEE 66th Annual Symposium on Foundations of Computer Science, FOCS 2025
    Pages565-584
    Number of pages20
    ISBN (Electronic)9798331571320
    DOIs
    StatePublished - 2025
    Event66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025 - Sydney, Australia
    Duration: 14 Dec 2025 → 17 Dec 2025

    Publication series

    NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
    ISSN (Print)0272-5428

    Conference

    Conference66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025
    Country/TerritoryAustralia
    CitySydney
    Period14/12/25 → 17/12/25

    Keywords

    • adaptive protocols
    • broadcast channel
    • interactive coding

    Fingerprint

    Dive into the research topics of 'Constant Rate Codes for Adaptive Broadcasts Do Not Exist'. Together they form a unique fingerprint.

    Cite this