On the noise sensitivity of monotone functions

Abstract It is known that for all monotone functions f : {0, 1} n → {0, 1}, if x ∈ {0, 1} n 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 ) ≠ f n ( y )] ≥ δ, 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 ) ≠ f n ( y )] ≥ δ, with: ϵ = c (δ) n −α for any α < 1/2, using the recursive majority function with arity k = k (α); ϵ = c (δ) n −1/2 log t n for t = log 2 $$\sqrt{\pi / 2}$$ = .3257 …, using an explicit recursive majority function with increasing arities; and ϵ = c (δ) n −1/2 , nonconstructively, following a probabilistic CNF construction due to Talagrand. We also study the problem of achieving the best dependence on δ in the case that the noise rate ϵ is at least a small constant; the results we obtain are tight to within logarithmic factors. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 333–350, 2003