Shotgun reconstruction in the hypercube
Michał Przykucki, Alexander Roberts, Alex Scott · Random Structures and Algorithms · 2021
Abstract Mossel and Ross raised the question of when a random coloring of a graph can be reconstructed from local information, namely, the colorings (with multiplicity) of balls of given radius. In this article, we are concerned with random 2‐colorings of the vertices of the ‐dimensional hypercube, or equivalently random Boolean functions. In the worst case, balls of diameter are required to reconstruct. However, the situation for random colorings is dramatically different: we show that almost every 2‐coloring can be reconstructed from the multiset of colorings of balls of radius 2. Furthermore, we show that for , almost every ‐coloring can be reconstructed from the multiset of colorings of 1‐balls.