CEU Electronic Theses and Dissertations, 2020
| Author | Galicza, Pál |
|---|---|
| Title | Noise Sensitivity, Pivotality and Clue for Transitive Functions on Spin Systems |
| Summary | In Chapter 1 we give a brief introduction into the analysis of Boolean functions. Several equivalent definitions of noise sensitivity are discussed. We highlight the complex relationship between noise sensitivity/stability and the pivotal set. In particular, answering a question of G. Kalai, we construct a noise stable sequence of monotone, transitive Boolean functions which have many pivotals with high probability. In Chapter 2 we introduce the central concept of our thesis. For a sequence of functions $f_n : \{-1,1\}^{V_n} \longrightarrow \R$ defined on increasing configuration spaces we talk about sparse reconstruction if there is a sequence of subsets $U_n \subseteq V_n$ of 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 for transitive functions no sparse reconstruction is possible. We discuss the question in different ways, measuring information content in $L^2$ and with entropy. We also highlight some interesting connections with cooperative game theory. Furthermore, we show that the left-right crossing event for critical planar percolation on the square lattice does not admit sparse reconstruction either. These results answer questions posed by I. Benjamini. Chapter 3 extends the question of sparse reconstruction to some larger classes of sequences of measures. We find that if the average correlation of spins in a sequence of spin systems decays slower than $1/|V_n|$, then sparse reconstruction is possible. We also investigate the question for sequences converging to a finitary factor of IID system and we find that the expected coding volume plays a crucial role in determining whether there is sparse reconstruction or not. Finally, we apply our results and methods to investigate Ising models on sequences of locally convergent graphs. We show that there is sparse reconstruction for low temperature and critical Ising models, and that there is no sparse reconstruction on the high temperature Curie-Weiss model. |
| Supervisor | Pete, Gábor |
| Department | Mathematics PhD |
| Full text | https://www.etd.ceu.edu/2020/galicza_pal.pdf |
Visit the CEU Library.
© 2007-2021, Central European University