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 [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]
Similarly to the probability that a single bit is revealed, we can talk about the number of bits revealed.
The cost [math]C_A[/math] of an algorithm is the expected size of [math]J_A[/math],
[math]C_A = \mathbb{E}[|J_A|].[/math]
The cost [math]C(f)[/math] of [math]f[/math] is cost of the best possible algorithm:
[math]C(f) = \inf_A C_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 converse is not true: The parity function is noise-sensitive, but its revealment is always 1 and does not tend to 0. The converse is not true even for monotone Boolean functions: For the right choice of parameters, the clique containment function is noise sensitive but its revealment is bounded away from 0. [3]
- The noise-sensitivity 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] [4]
- [math]C(f) \geq \mathrm{Inf}(f)^2[/math], and since [math]n \delta_f \geq C(f)[/math], we also have [math]\delta_f \geq \mathrm{Inf}(f)^2/n[/math]. [5]
- Functions with low revealment enjoy an improved Poincare inequality: If [math]f[/math] can be computed by a (randomized) decision tree where bit [math]i[/math] is queried with probability [math]\delta_i[/math], then
[math] \mathrm{Var}(f) \leq \sum_i \delta_i \mathrm{Inf}_i(f). [/math] [6]
- The above can be used to lower-bound the revealment: For a Boolean function [math]f:\{-1,1\}^n \to \{-1,1\}[/math],
[math] \delta_f \geq \mathrm{Var}(f)/(n \max_i \mathrm{Inf}_i(f)). [/math] [7]
References
- ↑ Theorem VIII.2 in Noise Sensitivity of Boolean functions and Percolation by C. Garban and J. Steif (2014).
- ↑ Corollary VIII.3 in Noise Sensitivity of Boolean functions and Percolation by C. Garban and J. Steif (2014).
- ↑ Proposition VIII.10 in Noise Sensitivity of Boolean functions and Percolation by C. Garban and J. Steif (2014).
- ↑ Corollary VIII.6 in Noise Sensitivity of Boolean functions and Percolation by C. Garban and J. Steif (2014).
- ↑ Theorem VIII.8 in Noise Sensitivity of Boolean functions and Percolation by C. Garban and J. Steif (2014).
- ↑ Theorem Every decision tree has an influential variable by O'Donnell, Sacks, Schramm and Servidio (2005)
- ↑ Theorem VIII.9 in Noise Sensitivity of Boolean functions and Percolation by C. Garban and J. Steif (2014).
