Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

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


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


TR21-160 | 15th November 2021
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Tight Bounds for General Computation in Noisy Broadcast Networks

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


TR22-095 | 5th July 2022
Meghal Gupta, Rachel Zhang

Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel

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


TR22-146 | 9th November 2022
Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai

Interactive Coding with Small Memory

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


TR23-066 | 4th May 2023
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Protecting Single-Hop Radio Networks from Message Drops

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


TR24-112 | 3rd July 2024
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

The Rate of Interactive Codes is Bounded Away from 1

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




ISSN 1433-8092 | Imprint