Is there any Boolean function from $\{-1,1\}^n$ to $\{-1,1\}$ such that whose noise sensitivity is greater than delta, where Delta is the probability of each bit is flipped in n-tupple.
Noise sensitivity of Boolean functions
2
$\begingroup$
combinatorics
probability-distributions
learning
-
0I don't at all understand your definition of Delta. – 2012-09-23
1 Answers
2
Take a look at Ryan O'Donnell's work, especially his PhD thesis on the noise sensitivity of Boolean functions:
- Computational applications of noise sensitivity (2003) [pdf]
You may also want to take a look at his blog on Boolean functions: