TY - GEN

T1 - The Rate of Interactive Codes Is Bounded Away from 1

AU - Efremenko, Klim

AU - Kol, Gillat

AU - Paramonov, Dmitry

AU - Saxena, Raghuvansh R.

N1 - Funding Information:
Klim Efremenko is supported by the Israel Science Foundation (ISF) through grant No. 1456/18 and European Research Council Grant number: 949707. Gillat Kol is supported by a National Science Foundation CAREER award CCF-1750443 and by a BSF grant No. 2018325.
Publisher Copyright:
© 2023 ACM.

PY - 2023/6/2

Y1 - 2023/6/2

N2 - 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 to0, 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. 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., "> 0. We mention that our result assumes a large alphabet set and resolves the (non-binary variant) of a conjecture by Haeupler [FOCS2014].

AB - 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 to0, 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. 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., "> 0. We mention that our result assumes a large alphabet set and resolves the (non-binary variant) of a conjecture by Haeupler [FOCS2014].

KW - Communication Complexity

KW - Error Correcting Codes

KW - Interactive Coding

UR - http://www.scopus.com/inward/record.url?scp=85163076228&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85163076228&partnerID=8YFLogxK

U2 - 10.1145/3564246.3585249

DO - 10.1145/3564246.3585249

M3 - Conference contribution

AN - SCOPUS:85163076228

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1424

EP - 1437

BT - STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing

A2 - Saha, Barna

A2 - Servedio, Rocco A.

PB - Association for Computing Machinery

T2 - 55th Annual ACM Symposium on Theory of Computing, STOC 2023

Y2 - 20 June 2023 through 23 June 2023

ER -