Binary Codes with Resilience Beyond 1/4 via Interaction

Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

In the reliable transmission problem, a sender, Alice, wishes to transmit a bit-string x to a remote receiver, Bob, over a binary channel with adversarial noise. The solution to this problem is to encode x using an error correcting code. As it is long known that the distance of binary codes is at most 1/2, reliable transmission is possible only if the channel corrupts (flips) at most a 1/4-fraction of the communicated bits.We revisit the reliable transmission problem in the two-way setting, where both Alice and Bob can send bits to each other. Our main result is the construction of two-way error correcting codes that are resilient to a constant fraction of corruptions strictly larger than 1/4. Moreover, our code has constant rate and requires Bob to only send one short message. We mention that our result resolves an open problem by Haeupler, Kamath, and Velingker [APPROX-RANDOM, 2015] and by Gupta, Kalai, and Zhang [STOC, 2022].Curiously, our new two-way code requires a fresh perspective on classical error correcting codes: While classical codes have only one distance guarantee for all pairs of codewords (i.e., the minimum distance), we construct codes where the distance between a pair of codewords depends on the 'compatibility' of the messages they encode. We also prove that such codes are necessary for our result.

Original languageEnglish (US)
Title of host publicationProceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
PublisherIEEE Computer Society
Pages1-12
Number of pages12
ISBN (Electronic)9781665455190
DOIs
StatePublished - 2022
Event63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 - Denver, United States
Duration: Oct 31 2022Nov 3 2022

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2022-October
ISSN (Print)0272-5428

Conference

Conference63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022
Country/TerritoryUnited States
CityDenver
Period10/31/2211/3/22

All Science Journal Classification (ASJC) codes

  • General Computer Science

Keywords

  • error correcting code
  • interactive communication
  • noise resilience

Fingerprint

Dive into the research topics of 'Binary Codes with Resilience Beyond 1/4 via Interaction'. Together they form a unique fingerprint.

Cite this