revealment

Revealment is a concept in the analysis of randomized algorithms for Boolean functions that measures how much an algorithm’s decision relies on any single input coordinate. It quantifies the likelihood that a coordinate is queried as the algorithm runs.

Formal definition: Let X = (X1, ..., Xn) be independent {0,1}-valued inputs with a common distribution μ. A randomized algorithm A reads coordinates of X adaptively and outputs F(X) for some Boolean function F: {0,1}^n → {0,1}. For each i, let Ri be the event that A queries Xi at least once during its execution. The revealment of A with respect to μ is Re(A) = max_i P(Ri), where the probability is over the randomness of X and of A. Some authors also use the supremum over i. A smaller revealment indicates that no single coordinate is frequently inspected by the algorithm.

Significance: Revealment relates to the structure of the function’s Fourier spectrum and to the influences of coordinates. If there exists an algorithm with small revealment, one can derive bounds on how much the function’s value is affected by changing individual inputs and relate these to noise sensitivity phenomena. The notion is particularly influential in probabilistic combinatorics and the study of threshold phenomena.

Applications: In percolation and related models, exploration or revealing procedures can have low revealment, meaning only a small fraction of edges or sites are inspected. This property helps in proving results about noise sensitivity and in understanding how global behavior emerges from local randomness. Revealment also informs analyses of decision-tree complexity and equilibrium between local and global influences in Boolean functions.

See also: influence, Fourier analysis of Boolean functions, noise sensitivity, decision trees, percolation.