Sparse reconstruction in spin systems. I: iid spins

Abstract For a sequence of Boolean functions fₙ: \{ - 1, 1\ ^{Vₙ}} \ - 1, 1\ f n: − 1, 1 V n → − 1, 1, defined on increasing configuration spaces of random inputs, we say that there is sparse reconstruction if there is a sequence of subsets U n ⊆ V n of the coordinates satisfying ∣ U n ∣ = o (∣ V n ∣) such that knowing the coordinates in U n gives us a non-vanishing amount of information about the value of f n. We first show that, if the underlying measure is a product measure, then no sparse reconstruction is possible for any sequence of transitive functions. We discuss the question in different frameworks, measuring information content in L 2 and with entropy. We also highlight some interesting connections with cooperative game theory. Beyond transitive functions, we show that the left-right crossing event for critical planar percolation on the square lattice does not admit sparse reconstruction either. Some of these results answer questions posed by Itai Benjamini.