Difference between revisions of "Revealment"
(Created page with "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...") |
(→Properties) |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 6: | Line 6: | ||
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>. | 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''' | + | 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>: |
:::{| class="wikitable" | :::{| class="wikitable" | ||
|- | |- | ||
| Line 17: | Line 17: | ||
|} | |} | ||
| + | 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>, | ||
| + | :::{| class="wikitable" | ||
| + | |- | ||
| + | |<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: | ||
| + | :::{| class="wikitable" | ||
| + | |- | ||
| + | |<math>C(f) = \inf_A C_A.</math> | ||
| + | |} | ||
== Properties == | == 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: | * 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: | ||
:::{| class="wikitable" | :::{| class="wikitable" | ||
|- | |- | ||
| − | |<math>E_f(k) \leq \delta_f k \|f\|^2.</math> <ref>Theorem VIII.2 in | + | |<math>E_f(k) \leq \delta_f k \|f\|^2.</math> <ref>Theorem VIII.2 in [https://arxiv.org/pdf/1102.5761.pdf Noise Sensitivity of Boolean functions and Percolation] by C. Garban and J. Steif (2014).</ref> |
|} | |} | ||
| − | * 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 sensitivity | noise sensitive]] <ref>Corollary VIII.3 in | + | * 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 sensitivity | noise sensitive]] <ref>Corollary VIII.3 in [https://arxiv.org/pdf/1102.5761.pdf Noise Sensitivity of Boolean functions and Percolation] by C. Garban and J. Steif (2014).</ref>. |
| − | * The | + | * 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. <ref>Proposition VIII.10 in [https://arxiv.org/pdf/1102.5761.pdf Noise Sensitivity of Boolean functions and Percolation] by C. Garban and J. Steif (2014).</ref> |
| + | |||
| + | * The noise-sensitivity statement can be made quantitative: Let <math>\delta_{f_n} \leq O(1/n^\beta)</math> for some <math>\beta>0</math> and let <math>\gamma < \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 | ||
:::{| class="wikitable" | :::{| class="wikitable" | ||
|- | |- | ||
|<math>\lim_{n\to\infty} \mathbb{E}[f_n(x)f_n(y)] - \mathbb{E}[f_n(x)]^2 = 0. | |<math>\lim_{n\to\infty} \mathbb{E}[f_n(x)f_n(y)] - \mathbb{E}[f_n(x)]^2 = 0. | ||
| − | </math> <ref>Corollary VIII.6 in | + | </math> <ref>Corollary VIII.6 in [https://arxiv.org/pdf/1102.5761.pdf Noise Sensitivity of Boolean functions and Percolation] by C. Garban and J. Steif (2014).</ref> |
|} | |} | ||
| + | |||
| + | * <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>. <ref>Theorem VIII.8 in [https://arxiv.org/pdf/1102.5761.pdf Noise Sensitivity of Boolean functions and Percolation] by C. Garban and J. Steif (2014).</ref> | ||
| + | |||
| + | * Functions with low revealment enjoy an improved [[Functional inequalities#Poincare inequality| 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 | ||
| + | :::{| class="wikitable" | ||
| + | |- | ||
| + | |<math> \mathrm{Var}(f) \leq \sum_i \delta_i \mathrm{Inf}_i(f). | ||
| + | |||
| + | </math> <ref>Theorem 1.1 in [https://ieeexplore.ieee.org/document/1530699 Every decision tree has an influential variable] by O'Donnell, Sacks, Schramm and Servidio (2005) </ref> | ||
| + | |} | ||
| + | |||
| + | * The above can be used to lower-bound the revealment: For a Boolean function <math>f:\{-1,1\}^n \to \{-1,1\}</math>, | ||
| + | :::{| class="wikitable" | ||
| + | |- | ||
| + | |<math> \delta_f \geq \mathrm{Var}(f)/(n \max_i \mathrm{Inf}_i(f)). | ||
| + | |||
| + | </math> <ref>Theorem VIII.9 in [https://arxiv.org/pdf/1102.5761.pdf Noise Sensitivity of Boolean functions and Percolation] by C. Garban and J. Steif (2014).</ref> | ||
| + | |} | ||
== References == | == References == | ||
<references/> | <references/> | ||
Latest revision as of 07:19, 15 February 2021
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 1.1 in 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).
