Broadcasting on Two-Dimensional Regular Grids
Broadcasting on Two-Dimensional Regular Grids
复制标题
在二维规则网格上广播
DOI：
10.1109/tit.2022.3177667
复制
发表时间：
2020
影响因子：
2.5
通讯作者：
Yury Polyanskiy
中科院分区：
文献类型：
--
作者：
A. Makur;Elchanan Mossel;Yury Polyanskiy
We study an important specialization of the general problem of broadcasting on directed acyclic graphs, namely, that of broadcasting on two-dimensional (2D) regular grids. Consider an infinite directed acyclic graph with the form of a 2D regular grid, which has a single source vertex <inline-formula> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula> at layer 0, and <inline-formula> <tex-math notation="LaTeX">$k + 1$ </tex-math></inline-formula> vertices at layer <inline-formula> <tex-math notation="LaTeX">$k \geq 1$ </tex-math></inline-formula>, which are at a distance of <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> from <inline-formula> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula>. Every vertex of the 2D regular grid has outdegree 2, the vertices at the boundary have indegree 1, and all other non-source vertices have indegree 2. At time 0, <inline-formula> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula> is given a uniform random bit. At time <inline-formula> <tex-math notation="LaTeX">$k \geq 1$ </tex-math></inline-formula>, each vertex in layer <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> receives transmitted bits from its parents in layer <inline-formula> <tex-math notation="LaTeX">$k-1$ </tex-math></inline-formula>, where the bits pass through independent binary symmetric channels with common crossover probability <inline-formula> <tex-math notation="LaTeX">$\delta \in \left({0,\frac {1}{2}}\right)$ </tex-math></inline-formula> during the process of transmission. Then, each vertex at layer <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> with indegree 2 combines its two input bits using a common deterministic Boolean processing function to produce a single output bit at the vertex. The objective is to recover <inline-formula> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula> with probability of error better than <inline-formula> <tex-math notation="LaTeX">$\frac {1}{2}$ </tex-math></inline-formula> from all vertices at layer <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> as <inline-formula> <tex-math notation="LaTeX">$k \rightarrow \infty $ </tex-math></inline-formula>. Besides their natural interpretation in the context of communication networks, such broadcasting processes can be construed as one-dimensional (1D) probabilistic cellular automata, or discrete-time statistical mechanical spin-flip systems on 1D lattices, with boundary conditions that limit the number of sites at each time <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> to <inline-formula> <tex-math notation="LaTeX">$k+1$ </tex-math></inline-formula>. Inspired by the literature surrounding the “positive rates conjecture” for 1D probabilistic cellular automata, we conjecture that it is impossible to propagate information in a 2D regular grid regardless of the noise level <inline-formula> <tex-math notation="LaTeX">$\delta $ </tex-math></inline-formula> and the choice of common Boolean processing function. In this paper, we make considerable progress towards establishing this conjecture, and prove using ideas from percolation and coding theory that recovery of <inline-formula> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula> is impossible for any <inline-formula> <tex-math notation="LaTeX">$\delta \in \left({0,\frac {1}{2}}\right)$ </tex-math></inline-formula> provided that all vertices with indegree 2 use either AND or XOR for their processing functions. Furthermore, we propose a detailed and general martingale-based approach that establishes the impossibility of recovering <inline-formula> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula> for any <inline-formula> <tex-math notation="LaTeX">$\delta \in \left({0,\frac {1}{2}}\right)$ </tex-math></inline-formula> when all NAND processing functions are used if certain structured supermartingales can be rigorously constructed. We also provide strong numerical evidence for the existence of these supermartingales by computing several explicit examples for different values of <inline-formula> <tex-math notation="LaTeX">$\delta $ </tex-math></inline-formula> via linear programming.
We study an important specialization of the general problem of broadcasting on directed acyclic graphs, namely, that of broadcasting on two-dimensional (2D) regular grids. Consider an infinite directed acyclic graph with the form of a 2D regular grid, which has a single source vertex <inline-formula> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula> at layer 0, and <inline-formula> <tex-math notation="LaTeX">$k + 1$ </tex-math></inline-formula> vertices at layer <inline-formula> <tex-math notation="LaTeX">$k \geq 1$ </tex-math></inline-formula>, which are at a distance of <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> from <inline-formula> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula>. Every vertex of the 2D regular grid has outdegree 2, the vertices at the boundary have indegree 1, and all other non-source vertices have indegree 2. At time 0, <inline-formula> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula> is given a uniform random bit. At time <inline-formula> <tex-math notation="LaTeX">$k \geq 1$ </tex-math></inline-formula>, each vertex in layer <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> receives transmitted bits from its parents in layer <inline-formula> <tex-math notation="LaTeX">$k-1$ </tex-math></inline-formula>, where the bits pass through independent binary symmetric channels with common crossover probability <inline-formula> <tex-math notation="LaTeX">$\delta \in \left({0,\frac {1}{2}}\right)$ </tex-math></inline-formula> during the process of transmission. Then, each vertex at layer <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> with indegree 2 combines its two input bits using a common deterministic Boolean processing function to produce a single output bit at the vertex. The objective is to recover <inline-formula> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula> with probability of error better than <inline-formula> <tex-math notation="LaTeX">$\frac {1}{2}$ </tex-math></inline-formula> from all vertices at layer <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> as <inline-formula> <tex-math notation="LaTeX">$k \rightarrow \infty $ </tex-math></inline-formula>. Besides their natural interpretation in the context of communication networks, such broadcasting processes can be construed as one-dimensional (1D) probabilistic cellular automata, or discrete-time statistical mechanical spin-flip systems on 1D lattices, with boundary conditions that limit the number of sites at each time <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> to <inline-formula> <tex-math notation="LaTeX">$k+1$ </tex-math></inline-formula>. Inspired by the literature surrounding the “positive rates conjecture” for 1D probabilistic cellular automata, we conjecture that it is impossible to propagate information in a 2D regular grid regardless of the noise level <inline-formula> <tex-math notation="LaTeX">$\delta $ </tex-math></inline-formula> and the choice of common Boolean processing function. In this paper, we make considerable progress towards establishing this conjecture, and prove using ideas from percolation and coding theory that recovery of <inline-formula> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula> is impossible for any <inline-formula> <tex-math notation="LaTeX">$\delta \in \left({0,\frac {1}{2}}\right)$ </tex-math></inline-formula> provided that all vertices with indegree 2 use either AND or XOR for their processing functions. Furthermore, we propose a detailed and general martingale-based approach that establishes the impossibility of recovering <inline-formula> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula> for any <inline-formula> <tex-math notation="LaTeX">$\delta \in \left({0,\frac {1}{2}}\right)$ </tex-math></inline-formula> when all NAND processing functions are used if certain structured supermartingales can be rigorously constructed. We also provide strong numerical evidence for the existence of these supermartingales by computing several explicit examples for different values of <inline-formula> <tex-math notation="LaTeX">$\delta $ </tex-math></inline-formula> via linear programming.
二维规则网格重建
DOI：
10.1109/isit45174.2021.9518174
发表时间：
2021
期刊：
IEEE International Symposium on Information Theory
影响因子：
--
作者：
Makur, Anuran;Mossel, Elchanan;Polyanskiy, Yury
通讯作者：
Polyanskiy, Yury
影响因子：
2
作者：
Holroyd A
通讯作者：
Holroyd A