Finitary Boolean functions
Examensarbete för masterexamen
We study functions on the infinite-dimensional Hamming cube (-1,1)**, in particu- lar Boolean functions into (-1,1), generalising results on analysis of Boolean functions on (-1,1); for n 2 N. The notion of noise sensitivity, first studied in [BKS99], is extended to this setting, and basic Fourier formulas are established. We also prove hypercontractivity estimates for these functions, and give a version of the Kahn-Kalai- Linial theorem giving a bound relating the total in uence to the maximal in uence. Particular attention is paid to so-called finitary functions, which are functions for which there exists an algorithm that almost surely queries only finitely many bits. Two versions of the Benjamini-Kalai-Schramm theorem characterizing noise sensitivity in terms of the sum of squared influences are given, under additional moment hypotheses on the amount of bits looked at by an algorithm. A version of the Kahn-Kalai-Linial theorem giving that the maximal influence is of order log(n) n is also given, replacing n with the expected number of bits looked at by an algorithm. Finally, we show that the result in [SS10] that revealments going to zero implies noise sensitivity also holds for finitary functions, and apply this to show noise sensitivity of a version of the voter model on suffciently sparse graphs.