2019/06/09 by Vilhelm Agdur, Agdur, Vilhelm
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #FOS: Mathematics #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1906.03709
openalex publication_date 2019/06/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study functions on the infinite-dimensional Hamming cube \-1,1\^∞, in particular Boolean functions into \-1,1\, generalising results on analysis of Boolean functions on \-1,1\n for n∈ℕ. The notion of noise sensitivity, first studied in arXiv:math/9811157 , 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 influence to the maximal influence. 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 arXiv:math/0504586 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 sufficiently sparse graphs.