Sparse reconstruction in spin systems. I: iid spins
Open Access
- 24 April 2024
- journal article
- research article
- Published by Springer Nature in Israel Journal of Mathematics
- Vol. 262 (1) , 43-96
Abstract
For a sequence of Boolean functions $${f_n}:{\{ - 1,1\} ^{{V_n}}} \to \{ - 1,1\} $$ , defined on increasing configuration spaces of random inputs, we say that there is sparse reconstruction if there is a sequence of subsets Un ⊆ Vn of the coordinates satisfying ∣Un∣ = o(∣Vn∣) such that knowing the coordinates in Un gives us a non-vanishing amount of information about the value of fn.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 L2 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.
Keywords
All Related Versions
This publication has 33 references indexed in Scilit:
- Towards a Proof of the Fourier-Entropy Conjecture?Geometric and Functional Analysis, 2020
- An Optimal Distributed Discrete Log Protocol with Applications to Homomorphic Secret SharingJournal of Cryptology, 2019
- A tail bound for read‐k families of functionsRandom Structures & Algorithms, 2014
- Superconcentration and Related Topics2014
- The Fourier Entropy–Influence Conjecture for Certain Classes of Boolean Functions2011
- Hunting for sharp thresholdsRandom Structures & Algorithms, 2004
- Noise sensitivity of boolean functions and applications to percolationPublications mathématiques de l'IHÉS, 1999
- Percolation1999
- Probability on Trees: An Introductory Climb1999
- Cores of convex gamesInternational Journal of Game Theory, 1971