| Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read (2005) | |||||||||||||||
Abstract | |||||||||||||||
| 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 Θ(n −1/2 √ log n). We give a balanced monotone Boolean function for which the corresponding probability is Θ(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 Θ(n −1/2). For balanced monotone Boolean functions, there is some input bit that is read with probability at least Θ(n −1/3). 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||