BLR Linearity testing

A function ${f: \mathbb{F}_{2}^{n} \rightarrow \mathbb{F}_{2}}$ is linear if either of the following conditions hold:
${f(x)=\sum_{i=1}^{n} a_{i} x_{i}}$ for some ${a_{i} \in \mathbb{F}_{2}}$ (Global description)
For all ${x, y \in \mathbb{F}_{2}^{n}, f(x+y)=f(x)+f(y)}$ (Local description)

What can we say about function which satisfies many of these local requirements? How close is it to a linear function? How does the distance to linear functions related to the fraction of local requirements satisfied?

BLR Test (Blum, Luby, Rubinfeld): Given ${f: \mathbb{F}_{2}^{n} \rightarrow \mathbb{F}_{2}}$ :

Choose ${x, y \in \mathbb{F}_{2}^{n}}$ independently and uniformly at random.
Query ${f(x), f(y), f(x+y)}$
Accept if ${f(x)+f(y)=f(x+y)}$ and Reject otherwise.

Theorem: Let ${f: \mathbb{F}_{2}^{n} \rightarrow \mathbb{F}_{2}}$ be a function whose distance to linear functions is ${\varepsilon}$ . Then the BLR test rejects ${f}$ with probability between ${\varepsilon}$ and ${5 \varepsilon .}$

Fourier Proof: Let $\displaystyle F(x)=(-1)^{f(x)}= \sum_{\alpha \in \mathbb{F}_{2}^{n}} \widehat{F}(\alpha)(-1)^{\langle\alpha, x\rangle}$

$\displaystyle \begin{aligned}{Pr}_{x, y}[f(x)+f(y)=f(x+y)] &=\frac{1}{2}+\frac{1}{2} \mathbb{E}_{x, y}[F(x) F(y) F(x+y)] \\ &=\frac{1}{2}+\frac{1}{2} \sum_{\alpha, \beta, \gamma \in \mathbb{F}_{2}^{n}} \widehat{F}(\alpha) \widehat{F}(\beta) \widehat{F}(\gamma) \mathbb{E}_{x, y}\left[(-1)^{\langle\alpha, x\rangle+\langle\beta, y\rangle+\langle\gamma, x+y\rangle}\right] \\ &=\frac{1}{2}+\frac{1}{2} \sum_{\alpha \in \mathbb{F}_{2}^{n}} \widehat{F}(\alpha)^{3} \end{aligned}$

Upper bound: Using Parseval ${ \sum \widehat{F}(\alpha)^{2}=\mathbb{E}\left[F(x)^{2}\right]=1 }$ , we get

$\displaystyle {Pr}_{x, y}[f(x)+f(y)=f(x+y)] \leq \frac{1}{2}\left(1+\max _{\alpha \in \mathbb{F}_{2}^{n}} \widehat{F}(\alpha)\right)$

We have for any

$\displaystyle \sum \widehat{F}(\alpha)^{2}=\mathbb{E}\left[F(x)^{2}\right]=1$

We have for any linear function

$\displaystyle L(x)=\langle x, \alpha\rangle \text { it holds that } {Pr}[f(x) \neq L(x)] \geq \varepsilon$ and hence

$\displaystyle \hat{F}(\alpha)=\mathbb{E}_{x}\left[F(x)(-1)^{\langle x, \alpha\rangle}\right]={Pr}[f(x)=L(x)]-{Pr}[f(x) \neq L(x)] \leq 1-2 \varepsilon$

$\displaystyle {Pr}_{x, y}[f(x)+f(y)=f(x+y)] \leq \frac{1}{2}\left(1+\max _{\alpha \in \mathbb{F}_{2}^{n}} \widehat{F}(\alpha)\right)\leq 1-\varepsilon$

$\displaystyle \implies {Pr}_{x, y}[f(x)+f(y)\neq f(x+y)] \geq \varepsilon$

Lower bound: Let ${\alpha'}$ be such that ${d(f, <\alpha',- >)=\varepsilon.}$

We have

$\displaystyle \hat{F}(\alpha')=1-2 \varepsilon$
$\displaystyle \widehat{F}\left(\alpha'\right)^{3} \geq 1-6 \varepsilon$
$\displaystyle \sum_{\alpha \neq \alpha^{'}}|\widehat{F}(\alpha)|^{3} \leq \sum_{\alpha \neq \alpha^{'}}|\widehat{F}(\alpha)|^{2}=1-\widehat{F}\left(\alpha^{'}\right)^{2} \leq 4 \varepsilon$
Therefore
$\displaystyle {Pr}_{x, y}[f(x)+f(y)=f(x+y)] \geq 1-5\varepsilon$