Broadcasting in random recursive dags

arXiv:2306.01727v2 Announce Type: replace-cross
Abstract: 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 …

abstract arxiv broadcasting cs.lg cs.si dag nodes parents probability random recursive stat.ml tree type uniform