Sparse reconstruction in spin systems I: iid spins
Authors:
- Pál GaliczaPGPál Galicza
- Gábor PeteGPGábor Pete
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Noise Sensitivity of Boolean Functions and Percolation2014
- The Fourier spectrum of critical percolationActa Mathematica, 2010
- Random-Turn Hex and Other Selection GamesThe American Mathematical Monthly, 2007
- Hunting for sharp thresholdsRandom Structures & Algorithms, 2004
- Introduction to the Theory of Cooperative Games2003
- Critical percolation in the plane: conformal invariance, Cardy's formula, scaling limitsComptes Rendus de l'Académie des Sciences - Series I - Mathematics, 2001
- Noise sensitivity of boolean functions and applications to percolationPublications mathématiques de l'IHÉS, 1999
- Some intersection theorems for ordered sets and graphsJournal of Combinatorial Theory, Series A, 1986
- Collective coin flipping, robust voting schemes and minima of Banzhaf values1985
- Cores of convex gamesInternational Journal of Game Theory, 1971