Consider two parties who wish to communicate in order to execute some interactive protocol \pi. However, the communication channel between them is noisy: An adversary sees everything that is transmitted over the channel and can change a constant fraction of the bits as he pleases, thus interrupting the execution of ... more >>>

Interactive coding, pioneered by Schulman (FOCS 1992, STOC 1993), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman, Gelles, Mao, and Ostrovsky ... more >>>

Multiparty interactive coding allows a network of n parties to perform distributed computations when the communication channels suffer from noise. Previous results (Rajagopalan and Schulman, STOC '94) obtained a multiparty interactive coding protocol, resilient to random noise, with a blowup of O(\log(\Delta+1)) for networks whose topology has a maximal degree ... more >>>

We study the effect of noise on the n-party beeping model. In this model, in every round, each party may decide to either `beep' or not. All parties hear a beep if and only if at least one party beeps. The beeping model is becoming increasingly popular, as it offers ... more >>>

We consider the celebrated radio network model for abstracting communication in wireless networks. In this model, in any round, each node in the network may broadcast a message to all its neighbors. However, a node is able to hear a message broadcast by a neighbor only if no collision occurred, ... more >>>

We devise a deterministic interactive coding scheme with rate 1-O(\sqrt{\varepsilon\log(1/\varepsilon)}) against \varepsilon-fraction of adversarial errors. The rate we obtain is tight by a result of Kol and Raz (STOC 2013). Prior to this work, deterministic coding schemes for any constant fraction \varepsilon>0 of adversarial errors could obtain rate no larger ... more >>>

A tree code is an edge-coloring of the complete infinite binary tree such that every two nodes of equal depth have a fraction--bounded away from 0--of mismatched colors between the corresponding paths to their least common ancestor. Tree codes were introduced in a seminal work by Schulman (STOC 1993) and ... more >>>

Interactive error correcting codes are codes that encode a two party communication protocol to an error-resilient protocol that succeeds even if a constant fraction of the communicated symbols are adversarially corrupted, at the cost of increasing the communication by a constant factor. What is the largest fraction of corruptions that ... more >>>

We study the error resilience of the message exchange task: Two parties, each holding a private input, want to exchange their inputs. However, the channel connecting them is governed by an adversary that may corrupt a constant fraction of the transmissions. What is the maximum fraction of corruptions that still ... more >>>

Let \Pi be a protocol over the n-party broadcast channel, where in each round, a pre-specified party broadcasts a symbol to all other parties. We wish to design a scheme that takes such a protocol \Pi as input and outputs a noise resilient protocol \Pi' that simulates \Pi over the ... more >>>

Given a noiseless protocol \pi_0 computing a function f(x, y) of Alice and Bob's private inputs x, y, the goal of interactive coding is to construct an error-resilient protocol \pi computing f such that even if some fraction of the communication is adversarially corrupted, both parties still learn f(x, y). ... more >>>

In this work, we design an interactive coding scheme that converts any two party interactive protocol \Pi into another interactive protocol \Pi', such that even if errors are introduced during the execution of \Pi', the parties are able to determine what the outcome of running \Pi would be in an ... more >>>

Single-hop radio networks (SHRN) are a well studied abstraction of communication over a wireless channel. In this model, in every round, each of the n participating parties may decide to broadcast a message to all the others, potentially causing collisions. We consider the SHRN model in the presence of stochastic ... more >>>

Kol and Raz [STOC 2013] showed how to simulate any alternating two-party communication protocol designed to work over the noiseless channel, by a protocol that works over a stochastic channel that corrupts each sent symbol with probability \epsilon>0 independently, with only a 1+\mathcal{O}(\sqrt{\H(\epsilon)}) blowup to the communication. In particular, this ... more >>>