Coding for interactive communication: A survey
R Gelles - … and Trends® in Theoretical Computer Science, 2017 - nowpublishers.com
Coding for interactive communication augments coding theory to the interactive setting:
instead of communicating a message from a sender to a receiver, here the parties are …
instead of communicating a message from a sender to a receiver, here the parties are …
Near-optimal communication Byzantine reliable broadcast under a message adversary
We address the problem of Reliable Broadcast in asynchronous message-passing systems
with n nodes, of which up to t are malicious (faulty), in addition to a message adversary that …
with n nodes, of which up to t are malicious (faulty), in addition to a message adversary that …
Low congestion cycle covers and their applications
A cycle cover of a bridgeless graph G is a collection of simple cycles in G such that each
edge e appears on at least one cycle. The common objective in cycle cover computation is …
edge e appears on at least one cycle. The common objective in cycle cover computation is …
Noisy beeps
K Efremenko, G Kol, RR Saxena - … of the 39th Symposium on Principles …, 2020 - dl.acm.org
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 …
each party may decide to either'beep'or not. All parties hear a beep if and only if at least one …
Distributed computations in fully-defective networks
We address fully-defective asynchronous networks, in which all links are subject to an
unlimited number of alteration errors, implying that all messages in the network may be …
unlimited number of alteration errors, implying that all messages in the network may be …
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 …
computations when the communication channels suffer from noise. Previous results …
Near-Optimal Fault Tolerance for Efficient Batch Matrix Multiplication via an Additive Combinatorics Lens
K Censor-Hillel, Y Machino, P Soto - International Colloquium on …, 2024 - Springer
Fault tolerance is a major concern in distributed computational settings. In the classic master-
worker setting, a server (the master) needs to perform some heavy computation which it may …
worker setting, a server (the master) needs to perform some heavy computation which it may …
Distributed CONGEST Algorithms against Mobile Adversaries
In their seminal PODC 1991 paper, Ostrovsky and Yung introduced the study of distributed
computation in the presence of mobile adversaries which can dynamically appear …
computation in the presence of mobile adversaries which can dynamically appear …
Efficient multiparty interactive coding for insertions, deletions, and substitutions
In the field of interactive coding, two or more parties wish to carry out a distributed
computation over a communication network that may be noisy. The ultimate goal is to …
computation over a communication network that may be noisy. The ultimate goal is to …
Explicit capacity approaching coding for interactive communication
We show an explicit (that is, efficient and deterministic) capacity approaching interactive
coding scheme that simulates any interactive protocol under random errors with nearly …
coding scheme that simulates any interactive protocol under random errors with nearly …