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 giv...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2023
|
| Online Access: | https://hdl.handle.net/1721.1/150312 |
| _version_ | 1826201930374840320 |
|---|---|
| author | Zhang, Rachel Yun |
| author2 | Kalai, Yael Tauman |
| author_facet | Kalai, Yael Tauman Zhang, Rachel Yun |
| author_sort | Zhang, Rachel Yun |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T11:59:06Z |
| format | Thesis |
| id | mit-1721.1/150312 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:59:06Z |
| publishDate | 2023 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1503122023-04-01T03:35:32Z The Optimal Error Resilience of Interactive Communication Over Binary Channels Zhang, Rachel Yun Kalai, Yael Tauman Vaikuntanathan, Vinod Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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. S.M. 2023-03-31T14:46:59Z 2023-03-31T14:46:59Z 2023-02 2023-02-28T14:36:05.568Z Thesis https://hdl.handle.net/1721.1/150312 0000-0001-6341-3505 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Zhang, Rachel Yun The Optimal Error Resilience of Interactive Communication Over Binary Channels |
| title | The Optimal Error Resilience of Interactive Communication Over Binary Channels |
| title_full | The Optimal Error Resilience of Interactive Communication Over Binary Channels |
| title_fullStr | The Optimal Error Resilience of Interactive Communication Over Binary Channels |
| title_full_unstemmed | The Optimal Error Resilience of Interactive Communication Over Binary Channels |
| title_short | The Optimal Error Resilience of Interactive Communication Over Binary Channels |
| title_sort | optimal error resilience of interactive communication over binary channels |
| url | https://hdl.handle.net/1721.1/150312 |
| work_keys_str_mv | AT zhangrachelyun theoptimalerrorresilienceofinteractivecommunicationoverbinarychannels AT zhangrachelyun optimalerrorresilienceofinteractivecommunicationoverbinarychannels |