Content deleted Content added
ClueBot NG (talk | contribs) m Reverting possible vandalism by Govind285 to version by Qetuth. False positive? Report it. Thanks, ClueBot NG. (845995) (Bot) |
No edit summary |
||
Line 4:
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).
my nam is govind
| |||