The Rate of Interactive Codes Is Bounded Away from 1
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
Abstract
Kol and Raz [STOC 2013] showed how to simulate any alternating two-party communication protocol designed to work over the noiseless channel, by a protocol that works over a stochastic channel that corrupts each sent symbol with probability є>0 independently, with only a 1+O(√(є)) blowup to the communication. In particular, this implies that the maximum rate of such interactive codes approaches 1 as є goes to 0, as is also the case for the maximum rate of classical error correcting codes. Over the past decade, followup works have strengthened and generalized this result to other noisy channels, stressing on how fast the rate approaches 1 as є goes to 0, but retaining the assumption that the noiseless protocol is alternating.
Ask about this paper
Ask your agent about it.
Lune has read the top-tier papers around this one, so every answer names the papers it rests on.
Your agent calls
Lunesearch_papers
Free to start. No credit card required.
Terminal
Install the CLIlune papers get 4130f8ab-28b4-4b6d-8038-4dbfc2564924Related papers
- Constant Rate Codes for Adaptive Broadcasts Do Not ExistKlim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. SaxenaFOCS 2025
- Tight Bounds for General Computation in Noisy Broadcast NetworksKlim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. SaxenaFOCS 2021 · 3 citations
- Binary Interactive Error Resilience Beyond (or why Klim Efremenko, Gillat Kol, Raghuvansh R. SaxenaFOCS 2020 · 4 citations
- Interactive error resilience beyond 2/7Klim Efremenko, Gillat Kol, Raghuvansh R. SaxenaSTOC 2020 · 5 citations
- Arikan meets Shannon: polar codes with near-optimal convergence to channel capacityVenkatesan Guruswami, Andrii Riazanov, Min YeSTOC 2020 · 16 citations
