Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

Radio Network Coding Requires Logarithmic Overhead

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

Revisions: 2 , Comments: 1

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

ISSN 1433-8092 | Imprint