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.