The Optimal Error Resilience of Interactive Communication Over Binary Channels

In interactive coding, Alice and Bob wish to compute some function f of their individual private inputs x and y. They do this by engaging in a non-adaptive (fixed order, fixed length) interactive protocol to jointly compute f(x,y). The goal is to do this in an error-resilient way, such that even given some fraction of adversarial corruptions to the protocol, both parties still learn f(x,y). We study the optimal error resilience of such a protocol in the face of adversarial bit flips or erasures. While the optimal error resilience of such a protocol over a large alphabet is well understood, the situation over the binary alphabet has remained open. Over the binary alphabet, there has remained a substantial gap in error resilience between the best protocol construction and the best known upper bound, for both bit flips and erasures. In this thesis, we construct protocols meeting the known upper bounds for both types of errors, thereby closing this gap and resolving the question of optimal error resilience for binary channels. Our schemes for both types of errors have positive rate and are computationally efficient.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2023

Author dc:creator

• Zhang, Rachel Yun

Advisors dc:contributor.advisor

• Kalai, Yael Tauman
• Vaikuntanathan, Vinod

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/150312

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/150312