Balanced Boolean function

In mathematics and computer science, a balanced boolean function is a boolean function whose output yields as many 0s as 1s over its input set. This means that for a uniformly random input string of bits, the probability of getting a 1 is 1/2.

An example of a balanced boolean function is the function that assigns a 1 to every even number and 0 to all odd numbers (likewise the other way around). The same applies for functions assigning 1 to all positive numbers and 0 otherwise.

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 construct a balanced monotone Boolean function and a randomized algorithm computing it for which each bit is read with probability Θ(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𔊪). For balanced monotone Boolean functions, there is some input bit that is read with probability at least Θ(n-1𔊫).

Usage

Balanced boolean functions are primarily used in [[cryptography Like a boss

See also

• Bent function

References

• Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read, Annual ACM Symposium on Theory of Computing