CEU Electronic Theses and Dissertations, 2019
| Author | Galicza, Pál |
|---|---|
| Title | Noise Stability versus Pivotals and Sparse Reconstruction of Functions in Spins Systems |
| Summary | First we define $f_n$ for all $n$ large enough so that the $d = \mathrm{Diam}(F)$-ball on $G_n$ and on $G$ are isomorphic. Observe that it is sufficient to give an injection from $F$ onto $G_n$. Pick an arbitrary $r \in F$, and again an arbitrary $r' \in V_n$. Using the (rooted) isomorphism between the $d$-balls of $r$ in $G$ and $r'$ in $G_n$, we can find a bijection between the vertices of a subset $F_n$ in $G_n$ and $F$. We start by proving the first statement. Define the sequence of ffIID measures $\nu_n$ on $G$ as follows. For every $v \in V$ we run the algorithm $\phi$ restricted to the ball $B_n(v)$. If the spin value $\sigma_{v}$ can be calculated from $B_n(v)$ (where $\sigma$ is distributed according to $\mu$), then we write the respective spin value, otherwise we flip a coin independent from everything else, according to the distribution of $\sigma_{v}$ conditioned on $B_n(v)$. It is clear that $\nu_n \xrightarrow{a. s.} \mu$ and that $\lim_{n \rightarrow \infty}{S_{\nu_n}(f)}= S_{\mu}(f)$. Therefore we can choose Fix a large number $L$ and choose a finite subset $H \subset \mathsf{Aut}(G)$ in such a way, that $\sum_{g \in H}{|\Cov(f, f^g)|} > L$. For an arbitrary $v \in F$ we may choose a large, but fix $r$ in such a way that $\bigcup_{g\in H} F^{g} \subseteq B_r(v) $. |
| Supervisor | Gabor, Pete |
| Department | Mathematics PhD |
| Full text | https://www.etd.ceu.edu/2019/galicza_pal.pdf |
Visit the CEU Library.
© 2007-2021, Central European University