The Taub Faculty of Computer Science Events and Talks

Interactive coding allows two or more parties to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop efficient coding schemes that tolerate a high level of noise while increasing the communication by only a constant factor (i.e., constant rate). In this work we provide computationally efficient, constant rate schemes that conduct any computation on arbitrary networks, and succeed with high probability in the presence of adversarial noise that can insert, delete, or alter communicated messages. Our schemes are the first computationally efficient schemes in the multiparty setting that are resilient to adversarial noise and the first to resist insertions and deletions in the multiparty setting. We first show a scheme that resist a fraction $\epsilon / m$ of adversarial noise, where $m$ is the number of links in the network and $\epsilon$ is some small constant. This scheme makes two assumptions: (a) every two parties hold a common random string, and (b) the noise is oblivious—it is fixed at the onset of the execution and is independent of the inputs and randomness held by the parties. We then show how to eliminate both assumptions albeit at the cost of slightly decreasing the resilience of our scheme to $\epsilon / m log m$.