The Influence of the ith variable on f : {-1,1}n ! {-1,1} measures how much f depends on the ith coordinate:
Ii(f) := P[f(x1,
,xi-1,-1,xi+1,
,xn) Ή f(x1,
xi-1,1,xi+1,
,xn)]
Let I(f) := maxi I(f) .
The h-Noise-Stability of f : {-1,1}n ! R is the correlation between the values of f on two inputs that are h-correlated:
Sh(f) := E[f(x) f(y)] where zi = (xi,yi) are independent with E[xi] = E[yi] = 0 and E[xi yi] = h (P[xi = yi] = (1+h)/2)
Definition of Ii and I extends to f : {-1,1}n ! R by:
Ii(f) := E[Vari[f]] = E[ Var[ f
| x1,
xi-1,xi+1,
,xn ] ]