Sparse reconstruction in spin systems. I: iid spins

For a sequence of Boolean functions f_n:{−1,1}^Vn→{−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² 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.