Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > INTERACTIVE CODING:
Reports tagged with Interactive Coding:
TR13-014 | 11th January 2013
Zvika Brakerski, Moni Naor

#### Fast Algorithms for Interactive Coding

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 >>>

TR17-079 | 1st May 2017
Alexander A. Sherstov, Pei Wu

#### Optimal Interactive Coding for Insertions, Deletions, and Substitutions

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 >>>

TR17-095 | 26th May 2017
Ran Gelles, Yael Tauman Kalai

#### Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks

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 >>>

TR19-111 | 16th August 2019
Klim Efremenko, Gillat Kol, Raghuvansh Saxena

#### Noisy Beeps

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 >>>

TR19-132 | 26th September 2019
Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Revisions: 1

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 >>>

TR19-147 | 31st October 2019
Gil Cohen, Shahar Samocha

#### Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors

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 >>>

TR20-014 | 16th February 2020
Gil Cohen, Shahar Samocha

#### Palette-Alternating Tree Codes

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 >>>

TR21-051 | 8th April 2021
Klim Efremenko, Gillat Kol, Raghuvansh Saxena

#### Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$)

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 >>>

TR21-060 | 8th April 2021
Klim Efremenko, Gillat Kol, Raghuvansh Saxena

#### Optimal Error Resilience of Adaptive Message Exchange

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 >>>

ISSN 1433-8092 | Imprint