Revealment
The revealment of a Boolean function [math]f[/math] is a notion which captures how important individual bits are in determining the value of a function. It is therefore similar in spirit to the influence, but is of a much more algorithmic flavor.
Definition
An algorithm for a Boolean function [math]f[/math] is a bit-querying algorithm, which, given [math]x \in \{-1,1\}^n[/math], returns the value [math]f(x)[/math]. In the process of its computation, it is allowed only to query the individual bits [math]x_i[/math] of [math]x[/math] one by one, revealing whether or not [math]x_i[/math] was [math]1[/math] or [math]-1[/math]. The choice of which bit to reveal in the [math]t[/math]-step is allowed to depend on all previous choices, and may also be randomized. For example, an algorithm for the dictator function needs only to query the dictating bit, while an algorithm for the address function can first query the address bits, then query the bit found at this address.
Let [math]J_A[/math] be the random set of bits that the algorithm [math]A[/math] queries when presented with a uniformly random input [math]x \sim \mu \{-1,1\}^n[/math]. Note that there is randomness both in the input [math]x[/math] and in the choices of [math]A[/math].
The revealment of an [math]\delta_A[/math] of a (randomized) algorithm [math]A[/math] is the maximum probability that a bit is queries by [math]A[/math]:
[math]\delta_A = \max_{i} \mathbb{P}[i \in J_A],[/math]
while the revealment [math]\delta[/math] of a function [math]f[/math] is revealment of the best possible algorithm:
[math]\delta = \inf_A \delta_A[/math]
Properties
- The Fourier spectrum at level [math]k[/math] of a Boolean function [math]f:\{-1,1\}^n \to \mathbb{R}[/math] can be bounded using revealment:
[math]E_f(k) \leq \delta_f k \|f\|^2.[/math] [1]
- If a series of Boolean functions [math]f_n[/math] satisfy [math]\delta_{f_n} \to 0 [/math], then [math]f_n[/math] is noise sensitive [2].
- The above statement can be made quantitative: Let [math]\delta_{f_n} \leq O(1/n^\beta)[/math] for some [math]\beta\gt 0[/math] and let [math]\gamma \lt \beta/2[/math]. If [math]x[/math] and [math]y[/math] are uniformly random in [math]\{-1,1\}^n[/math] and are [math]1/n^\gamma[/math]-correlated, then
[math]\lim_{n\to\infty} \mathbb{E}[f_n(x)f_n(y)] - \mathbb{E}[f_n(x)]^2 = 0. [/math] [3]
References
- ↑ Theorem VIII.2 in Garban, C., & Steif, J. (2014). Noise Sensitivity of Boolean Functions and Percolation (Institute of Mathematical Statistics Textbooks), Cambridge: Cambridge University Press. doi:10.1017/CBO9781139924160. https://arxiv.org/pdf/1102.5761.pdf
- ↑ Corollary VIII.3 in Garban, C., & Steif, J. (2014). Noise Sensitivity of Boolean Functions and Percolation (Institute of Mathematical Statistics Textbooks), Cambridge: Cambridge University Press. doi:10.1017/CBO9781139924160. https://arxiv.org/pdf/1102.5761.pdf
- ↑ Corollary VIII.6 in Garban, C., & Steif, J. (2014). Noise Sensitivity of Boolean Functions and Percolation (Institute of Mathematical Statistics Textbooks), Cambridge: Cambridge University Press. doi:10.1017/CBO9781139924160. https://arxiv.org/pdf/1102.5761.pdf
