Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Efficient Multiparty Interactive Coding for Insertions, Deletions and Substitutions
event speaker icon
Ran Gelles (Bar-Ilan University)
event date icon
Wednesday, 13.04.2022, 12:30
event location icon
Taub 601 Taub Bld.
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$.