Briend, SimonDevroye, LucLugosi, Gábor2025-06-172025-06-172025Briend S, Devroye L, Lugosi G. Broadcasting in random recursive dags. ESAIM Probab Stat. 2025;29:184-203. DOI: 10.1051/ps/20250021292-8100http://hdl.handle.net/10230/70708A uniform k-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-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).application/pdfengThis is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.info:eu-repo/semantics/article2025-06-17http://dx.doi.org/10.1051/ps/2025002Broadcasting problemaRandom recursive dagsNetwork archaeologyinfo:eu-repo/semantics/openAccess