Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-320 | 16th November 2026 16:46

Binary Two-Way Codes with Optimal Erasure Resilience

RSS-Feed




TR26-320
Authors: Klim Efremenko, Gillat Kol, Sergey Komech, Raghuvansh Saxena, Zhijun Zhang
Publication: 16th November 2026 18:09
Downloads: 13
Keywords: 


Abstract:

Two-way codes use communication in both directions to convey a message from a sender to a receiver over a noisy channel. In a beautiful work, [GKZ22] proved that for binary channels with adversarial erasures, interaction strictly outperforms one-way communication: they constructed a two-way code with erasure resilience approaching 3/5, surpassing the 1/2 upper bound for traditional binary codes implied by the Plotkin bound. They also proved that no binary two-way code can have erasure resilience greater than 2/3. Whether this bound could be approached remained a central open problem.

We resolve this problem in the affirmative by constructing a deterministic binary two-way code that approaches the optimal erasure resilience of 2/3 while achieving constant rate and linear encoding and decoding times. Our construction is remarkably simple and takes an entirely different approach from prior work.



ISSN 1433-8092 | Imprint