The NAND 2D regular-grid broadcasting conjecture

Let PXk+P_{X_k}^{+} and PXkP_{X_k}^{-} denote the distributions of the observations at layer kk conditioned on the source bit being 11 and 00, respectively. Fix δ(0,12)\delta\in\big(0,\frac{1}{2}\big), and suppose that every vertex with two inputs in the 2D regular grid uses the NAND Boolean rule. NAND broadcasting conjecture. Broadcasting is impossible, in the sense that

limkPXk+PXkTV=0.\lim_{k\rightarrow\infty}\left\|P_{X_k}^{+}-P_{X_k}^{-}\right\|_{\mathsf{TV}}=0.

This is a concrete special case of the broader 2D impossibility conjecture. The source presents it as a target for a martingale-based proof, so its resolution is not established in the supplied text.

Sources & referencesView supporting material

Primary source

Anuran Makur, Elchanan Mossel and Yury Polyanskiy, “Broadcasting on Two-Dimensional Regular Grids”, arXiv:2010.01390 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.