2018/08/02 by Ofer Grossman, Bernhard Haeupler, Grossman, Ofer +3
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1808.00838
openalex publication_date 2018/08/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The noisy broadcast model was first studied in [Gallager, TranInf'88] where an n-character input is distributed among n processors, so that each processor receives one input bit. Computation proceeds in rounds, where in each round each processor broadcasts a single character, and each reception is corrupted independently at random with some probability p. [Gallager, TranInf'88] gave an algorithm for all processors to learn the input in O(loglog n) rounds with high probability. Later, a matching lower bound of Ω(loglog n) was given in [Goyal, Kindler, Saks; SICOMP'08]. We study a relaxed version of this model where each reception is erased and replaced with a `?' independently with probability p. In this relaxed model, we break past the lower bound of [Goyal, Kindler, Saks; SICOMP'08] and obtain an O(log^* n)-round algorithm for all processors to learn the input with high probability. We also show an O(1)-round algorithm for the same problem when the alphabet size is Ω(poly(n)).