2
$\begingroup$

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.

  • 0
    I don't at all understand your definition of Delta.2012-09-23

1 Answers 1

2

Take a look at Ryan O'Donnell's work, especially his PhD thesis on the noise sensitivity of Boolean functions:

You may also want to take a look at his blog on Boolean functions: