Finitary Boolean functions
Typ
Examensarbete för masterexamen
Program
Publicerad
2019
Författare
Agdur, Vilhelm
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.