Compressing Communication in Distributed Protocols

Yael Tauman Kalai, Ilan Komargodski

We show how to compress communication in selection protocols, where the goal is to agree on a sequence of random bits using only a broadcast channel. More specifically, we present…