In this section we prove two theorems about the degree-$1$ Fourier weight of boolean functions: \[ \mathbf{W}^{1}[f] = \sum_{i=1}^n \widehat{f}(i)^2. \]
[...]
|
||||||
|
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 © 2013 Ryan O'Donnell -- All Rights Reserved |
||||||
Recent comments