Can I read On the Noise Sensitivity of Monotone Functions on EtoBox?

On the Noise Sensitivity of Monotone Functions by Elchanan Mossel; Ryan O'Donnell is a Mathematics article available to read on EtoBox.

What is On the Noise Sensitivity of Monotone Functions about?

## 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__)] 0. Previously, the best construction of monotone functions satisfying P[__f__~__n__~(__x__) ≠ __f__~__n__~(__y__)] ≥ δ, where 0 < δ 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

Who reads On the Noise Sensitivity of Monotone Functions?

Author

Elchanan Mossel; Ryan O'Donnell

Publisher

John Wiley and Sons; Wiley (John Wiley & Sons); John Wiley & Sons Inc.; Wiley (ISSN 1042-9832)

Published

2003

Language

EN

Field

Mathematics (Physical Sciences)