The NAND 2D regular-grid broadcasting conjecture

About 6 years old · traced to

Let PXk+P_{X_k}^{+} and PXk−P_{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

lim⁡k→∞∥PXk+−PXk−∥TV=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.

References

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.