For a Boolean function of independent coordinates and a randomized decision tree that determines it, the OSSS inequality bounds its variance by a sum of coordinate influences weighted by their revealment probabilities.
A decision tree adaptively reveals input coordinates until their observed values determine the output. Its revealment for a coordinate is the probability that the coordinate is inspected.
Choosing an intermediate radius uniformly and exploring the open cluster meeting that sphere gives a decision tree for a one-arm event. Translation and a union bound control each revealment by a constant times the average of the one-arm probabilities over the possible radii.
Articles by others on the same topic
There are currently no matching articles.