The Rate of Interactive Codes Is Bounded Away from 1
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
摘要
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.
问问这篇 Paper
问问你的智能体。
Lune 读过与它相关的顶会 Paper,每个回答都会注明依据哪几篇。
相关 Paper
- 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 次
- Binary Interactive Error Resilience Beyond (or why Klim Efremenko, Gillat Kol, Raghuvansh R. SaxenaFOCS 2020 · 被引用 4 次
- Interactive error resilience beyond 2/7Klim Efremenko, Gillat Kol, Raghuvansh R. SaxenaSTOC 2020 · 被引用 5 次
- Arikan meets Shannon: polar codes with near-optimal convergence to channel capacityVenkatesan Guruswami, Andrii Riazanov, Min YeSTOC 2020 · 被引用 16 次
