Withdraw
Loading…
An Upper Bound for Interactive ECCs with Separate Budgets
Nasa, Shreya; Song, Maoyuan
Loading…
Permalink
https://hdl.handle.net/2142/130316
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
61st Allerton Conference - 2025 PRIMARY
Manage Files
Loading…
Edit Collection Membership
Loading…
Edit Metadata
Loading…
Edit Properties
Loading…
Embargoes
Loading…