Shotgun reconstruction in the hypercube. Issue 1 (25th June 2021) - Przykucki, Michał; Roberts, Alexander; Scott, Alex
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 n ‐dimensional hypercube, or equivalently random Boolean functions. In the worst case, balls of diameter Ω ( n ) 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 q ≥ n 2 + ϵ, almost every q ‐coloring can be reconstructed from the multiset of colorings of 1‐balls.