Broadcasting in random recursive dags
This addresses a theoretical problem in random graph models and information propagation, with incremental contributions to understanding thresholds in noisy broadcasting.
The paper tackles the problem of estimating the majority bit among roots in a uniform k-dag with noisy propagation, identifying a threshold for the flip probability p as a function of k that determines whether majority rule yields an error below or above 1/2.
A uniform $k$-{\sc dag} generalizes the uniform random recursive tree by picking $k$ parents uniformly at random from the existing nodes. It starts with $k$ ''roots''. Each of the $k$ roots is assigned a bit. These bits are propagated by a noisy channel. The parents' bits are flipped with probability $p$, and a majority vote is taken. When all nodes have received their bits, the $k$-{\sc dag} is shown without identifying the roots. The goal is to estimate the majority bit among the roots. We identify the threshold for $p$ as a function of $k$ below which the majority rule among all nodes yields an error $c+o(1)$ with $c<1/2$. Above the threshold the majority rule errs with probability $1/2+o(1)$.