An Upper Bound for Interactive ECCs with Separate Budgets

Nasa, Shreya; Song, Maoyuan

Permalink

https://hdl.handle.net/2142/130316 Copy

Description

Title

An Upper Bound for Interactive ECCs with Separate Budgets

Author(s)

• Nasa, Shreya
• Song, Maoyuan

Issue Date

2025-09-17

Keyword(s)

• Coding theory
• Interactive error-correcting codes
• Impossibility upper bound
• Coding techniques and applications

Abstract

We study interactive error-correcting codes (iECCs) in the binary communication model with separate corruption budgets for both the directions of communication. Interactive error-correcting codes (iECCs) allow two parties, Alice and Bob, to communicate over a noisy channel through an interactive protocol, with the goal of communicating a message from Alice to Bob even when a bounded fraction of the communication is adversarially corrupted. In the standard one-way communication setting, previous works [1] show that an error fraction α of bit flips can be corrected to recover the original message if and only if α is bounded by 1/4 . Berlekamp [2] showed that this fraction improves to 1/3 with interaction using noiseless feedback. Elfremenko, Kol, Saxena and Zhang [3] further construct interactive error-correcting codes (iECCs) that can uniquely decode from an error fraction of 1/4 +10 [to the power of] −5 even in the presence of noisy feedback while the best known impossibility upper bound for this setting is 13/47 [4]. In order to better understand this gap, we study the communication model with independent corruption budgets for both sides of communication and show that no iECC can be resilient to more than 7/24 fraction of errors in this model.

Publisher

Allerton Conference on Communication, Control, and Computing

Series/Report Name or Number

2025 61st Allerton Conference on Communication, Control, and Computing Proceedings

ISSN

2836-4503

Type of Resource

Text

Genre of Resource

Conference Paper/Presentation

Language

eng

Handle URL

https://hdl.handle.net/2142/130316&&

Copyright and License Information

Copyright 2025 is held by Shreya Nasa and Maoyuan Song.

Owning Collections