Broadcasting on Random Directed Acyclic Graphs

Abstract

We study a generalization of the well-known model of broadcasting on trees. Consider a directed acyclic graph (DAG) with a unique source vertex $X$, and suppose all other vertices have indegree $d\ge 2$. Let the vertices at distance $k$ from $X$ be called layer $k$. At layer $0$, $X$ is given a random bit. At layer $k\ge 1$, each vertex receives $d$ bits from its parents in layer $k-1$, which are transmitted along independent binary symmetric channel edges, and combines them using a $d$-ary Boolean processing function. The goal is to reconstruct $X$ with probability of error bounded away from $1/2$ using the values of all vertices at an arbitrarily deep layer. This question is closely related to models of reliable computation and storage, and information flow in biological networks. In this paper, we analyze randomly constructed DAGs, for which we show that broadcasting is only possible if the noise level is below a certain degree and function dependent critical threshold. For $d\ge 3$, and random DAGs with layer sizes $\Omega (\log k)$ and majority processing functions, we identify the critical threshold. For $d=2$, we establish a similar result for NAND processing functions. We also prove a partial converse for odd $d\ge 3$ illustrating that the identified thresholds are impossible to improve by selecting different processing functions if the decoder is restricted to using a single vertex. Finally, for any noise level, we construct explicit DAGs (using expander graphs) with bounded degree and layer sizes $\Theta (\log k)$ admitting reconstruction. In particular, we show that such DAGs can be generated in deterministic quasi-polynomial time or randomized polylogarithmic time in the depth. These results portray a doubly-exponential advantage for storing a bit in DAGs compared to trees, where $d=1$ but layer sizes must grow exponentially with depth in order to enable broadcasting.

arXiv comment33 pages, double column format. arXiv admin note: text overlap with arXiv:1803.07527

References in corpus (6)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Reconstruction on trees and spin glass transition
• Robust reconstruction on trees is determined by the second eigenvalue
• Reconstruction of Random Colourings
• The critical Ising model on trees, concave recursions and nonlinear capacity
• Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise

Cited by in corpus (7)

• Coding Theorems for Noisy Permutation Channels
• Broadcasting on Two-Dimensional Regular Grids
• Doeblin Coefficients and Related Measures
• How heavy independent sets help to find arborescences with many leaves in DAGs
• Broadcasting on trees near criticality
• Information Spread with Error Correction
• Sufficient condition for root reconstruction by parsimony on binary trees with general weights