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

Details Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read

2004-10-12

arxiv.org/abs/math/0410282v1

Mathematics

Probability

11 pages

Scientific paper

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}).

Affiliated with

Also associated with

No associations

Rating

Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-718696