Shotgun reconstruction in the hypercube. Issue 1 (25th June 2021)

• Record Type: Journal Article
• Authors: Przykucki, Michał; Roberts, Alexander; Scott, Alex
• Is Part Of: Random structures & algorithms. Volume 60:Issue 1(2022)
• Page Start: 117
• Page End: 150
• Publication Date: 2021-06-25
• Subjects: random colorings -- shotgun reconstruction -- vertex‐isoperimetric stability; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21028
• Languages: English
• ISSNs: 1042-9832

Abstract

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.