Showing 2021Show all
2 papers · 1 filter
cs.DS2021
Interactive Error Correcting Codes Over Binary Erasure Channels Resilient to Adversarial Corruption
Meghal Gupta, Yael Tauman Kalai, Rachel Zhang
An error correcting code () allows a sender to send a message to a receiver such that even if a constant fraction of the communicated bits are corrupted, the receiver…
cs.DS2021
The Optimal Error Resilience of Interactive Communication Over Binary Channels
Meghal Gupta, Rachel Yun Zhang
In interactive coding, Alice and Bob wish to compute some function of their individual private inputs and . They do this by engaging in a non-adaptive (fixed order, fixe…