| 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 Pf(x) ≠ f(y)] < cn?α+1/2, for some c > 0. Previously, the best construction of monotone functions satisfying Pfn(x) ≠ fn(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, Pfn(x) ≠ fn(y)] ≥ δ, with: - ? = c(δ)n?α for any α < 1/2, using the recursive majority function with arity k = k(α);
- ? = c(δ)n?1/2logtn for t = log2
 = .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 |
