2024/06/13 by Pál Galicza, Galicza, Pál, Gábor Pete +1 · 1 citation
Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Dynamical Systems (math.DS) #FOS: Mathematics #FOS: Physical sciences #Markov Chains and Monte Carlo Methods #Mathematical Physics (math-ph) #Probability (math.PR) #Quantum many-body systems #Theoretical and Computational Physics
paper · pdf · doi:10.48550/arxiv.2406.09232
openalex publication_date 2024/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a sequence of Boolean functions fn : \-1, 1\Vn \longrightarrow \-1, 1\, with random input given by some probability measure ℙn, we say that there is sparse reconstruction for fn if there is a sequence of subsets Un ⊆ Vn of coordinates satisfying |Un| = o(|Vn|) such that knowing the spins in Un gives us a non-vanishing amount of information about the value of fn. In the first part of this work, we showed that if the ℙns are product measures, then no sparse reconstruction is possible for any sequence of transitive functions. In this sequel, we consider spin systems that are relatives of IID measures in one way or another, with our main focus being on the Ising model on finite transitive graphs or exhaustions of lattices. We prove that no sparse reconstruction is possible for the entire high temperature regime on Euclidean boxes and the Curie-Weiss model, while sparse reconstruction for the majority function of the spins is possible in the critical and low temperature regimes. We give quantitative bounds for two-dimensional boxes and the Curie-Weiss model, sharp in the latter case. The proofs employ several different methods, including factor of IID and FK random cluster representations, strong spatial mixing, a generalization of discrete Fourier analysis to Divide-and-Color models, and entropy inequalities.