Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read
<|reference_start|>Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read: A Boolean function of n bits is balanced if it takes the value 1 with probability 1/2. We exhibit a balanced Boolean function with a randomized evaluation procedure (with probability 0 of making a mistake) so that on uniformly random inputs, no input bit is read with probability more than Theta(n^{-1/2} sqrt{log n}). We give a balanced monotone Boolean function for which the corresponding probability is Theta(n^{-1/3} log n). We then show that for any randomized algorithm for evaluating a balanced Boolean function, when the input bits are uniformly random, there is some input bit that is read with probability at least Theta(n^{-1/2}). For balanced monotone Boolean functions, there is some input bit that is read with probability at least Theta(n^{-1/3}).<|reference_end|>
@article{benjamini2004balanced,
    title={Balanced Boolean functions that can be evaluated so that every input bit
  is unlikely to be read},
    author={Itai Benjamini, Oded Schramm, David B. Wilson},
    journal={Proc. 37th ACM Symposium on Theory of Computing (STOC), pages
  244--250, 2005},
    year={2004},
    doi={10.1145/1060590.1060627},
    archivePrefix={arXiv},
    eprint={math/0410282},
    primaryClass={math.PR cs.CC}
}