Broadcasting on Two-Dimensional Regular Grids

DOI10.1109/TIT.2022.3177667MaRDI QIDQ6195675zbMATH OpenOpenAlexWikidataFDO

Authors Anuran Makur, Elchanan Mossel, Yury Polyanskiy

Publication date 14 March 2024

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

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

zbMATH Keywords

broadcastinginfinite directed acyclic graphlinear codelinear programmingoriented bond percolationpotential functionprobabilistic cellular automatasupermartingale

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Algebraic theory of languages and automata (68Q70)

Abstract: We study a specialization of the problem of broadcasting on directed acyclic graphs, namely, broadcasting on 2D regular grids. Consider a 2D regular grid with source vertex $X$ at layer $0$ and $k+1$ vertices at layer $kgeq1$, which are at distance $k$ from $X$. Every vertex of the 2D regular grid has outdegree $2$, the vertices at the boundary have indegree $1$, and all other vertices have indegree $2$. At time $0$, $X$ is given a random bit. At time $kgeq1$, each vertex in layer $k$ receives transmitted bits from its parents in layer $k-1$, where the bits pass through binary symmetric channels with noise level $deltain(0,1/2)$. Then, each vertex combines its received bits using a common Boolean processing function to produce an output bit. The objective is to recover $X$ with probability of error better than $1/2$ from all vertices at layer $k$ as $kightarrowinfty$. Besides their natural interpretation in communication networks, such broadcasting processes can be construed as 1D probabilistic cellular automata (PCA) with boundary conditions that limit the number of sites at each time $k$ to $k+1$. We conjecture that it is impossible to propagate information in a 2D regular grid regardless of the noise level and the choice of processing function. In this paper, we make progress towards establishing this conjecture, and prove using ideas from percolation and coding theory that recovery of $X$ is impossible for any $delta$ provided that all vertices use either AND or XOR processing functions. Furthermore, we propose a martingale-based approach that establishes the impossibility of recovering $X$ for any $delta$ when all NAND processing functions are used if certain supermartingales can be rigorously constructed. We also provide numerical evidence for the existence of these supermartingales by computing explicit examples for different values of $delta$ via linear programming.

Cited in

(1)

• Gaussian broadcast on grids

This page was built for publication: Broadcasting on Two-Dimensional Regular Grids

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