In Chapter 8.4 we described the problem of “threshold phenomena” for monotone functions $f : \{1,1\}^n \to \{1,1\}$.
[...]


In Chapter 8.4 we described the problem of “threshold phenomena” for monotone functions $f : \{1,1\}^n \to \{1,1\}$. [...] In this section we will revisit a number of combinatorial/probabilistic notions and show that for functions $f \in L^2(\Omega^n, \pi^{\otimes n})$, these notions have familiar Fourier formulas which don’t depend on the Fourier basis. [...] A very important quantity in the analysis of a boolean function is the sum of its influences. Definition 26 The total influence of $f : \{1,1\}^n \to {\mathbb R}$ is defined to be \[ \mathbf{I}[f] = \sum_{i=1}^n \mathbf{Inf}_i[f]. \] [...] 

Copyright © 2015 Ryan O'Donnell  All Rights Reserved 
Recent comments