# Broadcasting in random recursive dags

arXiv: https://arxiv.org/abs/2306.01727 · HTML: https://mlsanity.com/paper/2306.01727/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 24 references that are in the map.
- First posted on arXiv 2 Jun 2023.

## Builds on (most cited first, 2 of 2)

- [Archaeology of random recursive dags and Cooper-Frieze random networks](https://mlsanity.com/paper/2207.14601/) (2022)
- [Coexistence in preferential attachment networks](https://mlsanity.com/paper/1307.2893/) (2013)

## Built on by (most cited first, 1 of 1)

- [Errors are Robustly Tamed in Cumulative Knowledge Processes](https://mlsanity.com/paper/2309.05638/) (2023)

## Abstract (arXiv)

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).