Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-112 | 3rd July 2024 17:09

The Rate of Interactive Codes is Bounded Away from 1

RSS-Feed

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 $\epsilon>0$ independently, with only a $1+\mathcal{O}(\sqrt{\H(\epsilon)})$ blowup to the communication. In particular, this implies that the maximum rate of such interactive codes approaches $1$ as $\epsilon$ 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 $\epsilon$ goes to $0$, but retaining the assumption that the noiseless protocol is alternating.

In this paper we consider the general case, where the noiseless protocols can have arbitrary orders of speaking. In contrast to Kol-Raz and to the followup results in this model, we show that the maximum rate of interactive codes that encode general protocols is upper bounded by a universal constant strictly smaller than $1$. To put it differently, we show that there is an inherent blowup in communication when protocols with arbitrary orders of speaking are faced with any constant fraction of errors $\epsilon > 0$. We mention that our result assumes a large alphabet set and resolves the (non-binary variant) of a conjecture by Haeupler [FOCS 2014].



ISSN 1433-8092 | Imprint