Broadcasting on Random Directed Acyclic Graphs

DOI10.1109/TIT.2019.2935772MaRDI QIDQ5211634zbMATH OpenOpenAlexFDO

Authors Anuran Makur, Elchanan Mossel, Yury Polyanskiy

Publication date 28 January 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.03946

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Communication theory (94A05)

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 $dgeq2$. Let the vertices at distance $k$ from $X$ be called layer $k$. At layer $0$, $X$ is given a random bit. At layer $kgeq1$, 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 $dgeq3$, and random DAGs with layer sizes $Omega(logk)$ 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 $dgeq3$ 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(logk)$ 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.

Recommendations

• Broadcasting in random graphs
• Broadcasting in random graphs
• Optimal and near-optimal broadcast in random graphs
• Broadcasting on random recursive trees
• Close-to-optimal and near-optimal broadcasting in random graphs
• Randomized broadcast in networks
• Broadcasting in Bounded Degree Graphs

Cited in

(12)

• Broadcasting in DMA-bound bounded degree graphs
• Sufficient condition for root reconstruction by parsimony on binary trees with general weights
• Broadcasting on random recursive trees
• How heavy independent sets help to find arborescences with many leaves in DAGs
• On Radio Broadcasting in Random Geometric Graphs
• Galton-Watson processes and their role as building blocks for branching processes
• Broadcasting in random graphs
• Combinatorial statistics and the sciences
• Is this correct? Let's check!
• Broadcasting in random recursive DAGs
• Likelihood-based root state reconstruction on a tree: sensitivity to parameters and applications
• Optimal and near-optimal broadcast in random graphs

This page was built for publication: Broadcasting on Random Directed Acyclic Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211634)