Reconstructing Random Pictures
Bhargav P. Narayanan, Corrine Yap · Random Structures and Algorithms · 2025
ABSTRACT Given a random binary picture of size , that is, an grid filled with zeros and ones uniformly at random, when is it possible to reconstruct from its ‐deck, that is, the multiset of all its subgrids? We demonstrate “two‐point concentration” for the reconstruction threshold by showing that there is an integer such that if , then is reconstructible from its ‐deck with high probability, and if , then with high probability, it is impossible to reconstruct from its ‐deck. The proof of this result uses a combination of interface‐exploration arguments and entropic arguments.