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 …

Near-optimal communication Byzantine reliable broadcast under a message adversary

T Albouy, D Frey, R Gelles, C Hazay… - … on Principles of …, 2025 - drops.dagstuhl.de
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 …

Low congestion cycle covers and their applications

M Parter, E Yogev - Proceedings of the Thirtieth Annual ACM-SIAM …, 2019 - SIAM
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 …

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 …

Distributed computations in fully-defective networks

K Censor-Hillel, S Cohen, R Gelles… - Proceedings of the 2022 …, 2022 - dl.acm.org
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 …

Constant-rate interactive coding is impossible, even in constant-degree networks

R Gelles, YT Kalai - IEEE Transactions on Information Theory, 2019 - ieeexplore.ieee.org
Multiparty interactive coding allows a network of n parties to perform distributed
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 …

Distributed CONGEST Algorithms against Mobile Adversaries

O Fischer, M Parter - Proceedings of the 2023 ACM Symposium on …, 2023 - dl.acm.org
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 …

Efficient multiparty interactive coding for insertions, deletions, and substitutions

R Gelles, YT Kalai, G Ramnarayan - … of the 2019 ACM Symposium on …, 2019 - dl.acm.org
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 …

Explicit capacity approaching coding for interactive communication

R Gelles, B Haeupler, G Kol… - IEEE Transactions …, 2018 - ieeexplore.ieee.org
We show an explicit (that is, efficient and deterministic) capacity approaching interactive
coding scheme that simulates any interactive protocol under random errors with nearly …