| Paper ID | D5-S2-T3.2 |
| Paper Title |
Reconstruction on 2D Regular Grids |
| Authors |
Anuran Makur, Elchanan Mossel, Yury Polyanskiy, Massachusetts Institute of Technology, United States |
| Session |
D5-S2-T3: Reconstruction on Graphs |
| Chaired Session: |
Friday, 16 July, 22:20 - 22:40 |
| Engagement Session: |
Friday, 16 July, 22:40 - 23:00 |
| Abstract |
We investigate the problem of broadcasting a bit on a 2D regular grid. Consider a directed acyclic graph with the structure of a 2D regular grid, which has a single source vertex $X$ at layer $0$, and $k + 1$ vertices at distance of $k \geq 1$ from $X$ at layer $k$. Every vertex has outdegree $2$, the boundary vertices have indegree $1$, and the interior vertices have indegree $2$. At time $0$, $X$ is given a uniform random bit. At time $k \geq 1$, each vertex in layer $k$ receives bits from its parents in layer $k-1$, where the bits pass through binary symmetric channels with crossover probability $\delta \in \big(0,\frac{1}{2}\big)$. Each vertex with indegree $2$ then combines its input bits with a common Boolean processing function to produce its output bit. The goal is to reconstruct $X$ with probability of error less than $\frac{1}{2}$ from all vertices at layer $k$ as $k \rightarrow \infty$. Besides their natural interpretation in communication networks, such stochastic processes can be construed as 1D probabilistic cellular automata (PCA) with boundary conditions on the number of sites per layer. Inspired by the "positive rates conjecture" for 1D PCA, we establish that reconstruction of $X$ is impossible for any $\delta$ provided that either AND or XOR gates are employed as the common processing function. Furthermore, we show that if certain structured supermartingales exist, reconstruction is impossible for any $\delta$ when a common NAND processing function is used. We also provide numerical evidence for the existence of these supermartingales using linear programming.
|
