Indistinguishable sceneries on the Boolean hypercube

Renan Gross, Uri Grupel

Published 2017-01-26Version 1

We show that the scenery reconstruction problem on the Boolean hypercube is in general impossible. This is done by using locally biased functions, in which every vertex has a constant fraction of neighbors colored by $1$, and locally stable functions, in which every vertex has a constant fraction of neighbors colored by its own color. Our methods are constructive, and also give super-polynomial lower bounds on the number of locally biased and locally stable functions. We further show similar results for $\mathbb{Z}^n$ and other graphs, and offer several follow-up questions.