Lune

STOC2023Top-tier venue

The Rate of Interactive Codes Is Bounded Away from 1

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena

2023Year

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.

Questions to start from

Your agent calls

Lunesearch_papers

Ask in Lune

Free to start. No credit card required.

lune papers get 4130f8ab-28b4-4b6d-8038-4dbfc2564924

Related papers

Dusk over the sea between two cliffs drawn in fine vertical lines