| On the Noise Sensitivity of Monotone Functions (2003) | |||||||||||||||
Abstract | |||||||||||||||
| It is known that for all monotone functions f : {0, 1}, if x is chosen uniformly at random and y is obtained from x by flipping each of the bits of x independently with probability # = n -# , then P[f(x) f(y)] < cn -#+1/2 , for some c > 0. Previously, the best construction of monotone functions satisfying P[f n (x) where 0 < # < 1/2, required # c(#)n -# , where # = 1 ln 2/ ln 3 = 0.36907. . . , and c(#) > 0. We improve this result by achieving for every 0 < # < 1/2, P[f n (x) #, with: . | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||