Quantitative relation between noise sensitivity and influences

Nathan Keller, Guy Kindler

A Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is said to be noise sensitive if inserting a small random error in its argument makes the value of the function almost unpredictable. B…