Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read.

Itai Benjamini Oded Schramm David Bruce Wilson

Published in: STOC (2005)

Keyphrases

boolean functions
uniform distribution
prime implicants
membership queries
threshold functions
functional properties
relevant variables
linear threshold
read once formulas
dnf formulae
multi valued
bi decomposition
sample size
pac learning
truth table
pseudo boolean functions