  For a sequence of Boolean functions $f_n : \{-1,1\}^{V_n} \longrightarrow
\{-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
\subseteq 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.
