Leírás
We say that a sequence of measures on the configuration space \{-1,1\}^{V_n} of some sequence of finite transitive graphs G_n(V_n, E_n) admits sparse reconstruction if there is a sequence of transitive functions f_n and some subsets U_n of V_n with density going to 0, such that learning the bits in U_n gives a non-vanishing information about the output of f_n. We consider different information measures, one using L^2 distance, another using entropy, and show that for product measures there is no sparse reconstruction in either case. We investigate the same question for the sequence of Ising measures on d-dimensional tori and the complete graph, and for sequences of measures tending to a finitary factor of IID measure on \Z^d. Joint work with Gábor Pete.