Binary Codes with Resilience Beyond 1/4 via Interaction

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.

Authors

• Klim Efremenko
• Gillat Kol
• Raghuvansh R. Saxena
• Zhijun Zhang 0007

Keywords

• Computer science
• Binary codes
• Receivers
• Error correction codes
• Reliability
• Resilience
• Binary Code
• Minimum Distance
• Codeword
• Reliable Transmission
• Transmission Problem
• Binary Channel
• Elements
• Communication Protocol
• Pair Formation
• Binary String
• Hamming Distance
• Random Code
• Least Significant Bit
• Most Significant Bit
• Noisy Channels
• Feedback Channel
• Single Message
• Noise Tolerance
• Fractional Error
• error correcting code
• interactive communication
• noise resilience