Resilience

Definition

For a set of indices [math]S\subseteq [n][/math] and an assignment of variables [math]z\in\{-1,1\}^S[/math], let [math]X_S[/math] be the random variable whose bits indexed by [math]j \in S[/math] are fixed to [math]z_j[/math], and the rest of bits are independent and uniform.

A function [math]f:\{-1,1\}^n \to \mathbb{R}[/math] is called [math](r,\alpha)[/math]-resilient if

[math]\begin{align*}\left|\mathbb{E}[f\mid S_S = z] - \mathbb{E}[f]\right| \leq \alpha && \forall |S|\leq r, z\in\{-1,1\}^S \end{align*}[/math]

In words, restricting any set of [math]\leq r[/math] bits to any value does not significantly change the expectation of the function.

Properties

• If the [math] \max \{ \hat{f}(S) \mid 0\lt |S|\leq r\} \leq 2^{-r}\alpha[/math], then [math]f[/math] is [math](r,\alpha)[/math]-resilient.