The BLR linearity test over F_2

Let $n\ge 0$ and let $f:{\mathbb{F}}_2^n\to {\mathbb{F}}_2$ be a fixed oracle table. Here ${\mathbb{F}}_2=\{0,1\}$ has addition and multiplication modulo two, with the field convention of Field. For $a,x\in {\mathbb{F}}_2^n$, put $a\cdot x={\sum }_i{a}_i{x}_i$ modulo two. A linear function here is ${\mathrm{\ell }}_a(x)=a\cdot x$; no affine constant is added.

The BLR test chooses independent uniform $x,y\in {\mathbb{F}}_2^n$, queries $f(x),f(y),f(x+y)$, and accepts exactly when $f(x)+f(y)=f(x+y)\mathrm{.}$ It uses three oracle calls (locations can coincide) and $2n$ random bits. Its acceptance probability is over the two uniform choices, with $f$ fixed.

The normalized distance is $\mathrm{dist}(f,g)=2^{-n}\mathrm{\mid }\{x:f(x)\mathrm{\ne }g(x)\}\mathrm{\mid }$. Agreement is $1-\mathrm{dist}(f,g)$; distance to linear functions is ${\min }_a\mathrm{dist}(f,{\mathrm{\ell }}_a)$. The ordered truth table of ${\mathrm{\ell }}_a$ is the Walsh–Hadamard encoding of $a$, a string of length $2^n$. When $n=0$, the cube has one point and the sole linear function is zero.