BLR Linearity Test for Boolean Functions
Linear Functions
A function \(f\colon F_2^n \to F_2\) is linear if \(f(x+y) = f(x) +f(y)\) for all \(x,y\in F_2^n\). Equivalently, \(f\) is linear if and only if there exists \(a\in F_2^n\) such that \(f(x) = ax\), or there exists \(S\subseteq [n]\) such that \(f(x) = \sum_{i\in S} x_i\).
Note that \(x\) can be expressed as \(x = \sum_{i=1}^n x_i e_i\), where each \(e_i\) is a unit vector. A linear function \(f\) decomposes as \(f(x) = f (\sum_{i=1}^n x_i e_i) = \sum_{i=1}^n x_i f(e_i)\).
We say a function \(f\colon F_2^n \to \pm 1\) is linear if there is \(\alpha\in F_2^n\) such that \(f(x) = (-1)^{\alpha x}\). Equivalently, \(f\) is linear if and only if \(f(x+y) = f(x)f(y)\) for all \(x,y\in F_2^n\).
We say two functions \(f, g\colon F_2^n \to \pm 1\) are \(\epsilon\)-close if they disagree on at most \(\epsilon\) fraction of inputs. It holds that \(f, g\) are \(\epsilon\)-close if and only if \(\langle f,g \rangle \geq 1-2\epsilon\). A function \(f\) is \(\epsilon\)-close to linear if there is a linear function \(g\) such that \(f\) and \(g\) are \(\epsilon\)-close.
Linearity Testing
The linearity testing problem is to check whether a function is (close to) linear by asking oracle queries to the function. The BLR (Blum-Luby-Rubinfeld) test is defined as follows: Pick up \(x,y\in F_2^n\) randomly, and accept if and only if \(f(x+y) = f(x) f(y)\). Note that there are three queries asked here. The probability that \(f\) passes the test is
\[
\Pr_{x,y\in F_2^n}[f(x+y) = f(x) f(y)].
\]
It turns out this probability characterizes how close \(f\) is to linear.
Theorem. If \(\Pr_{x,y\in F_2^n}[f(x+y) = f(x) f(y)] \geq 1 – \epsilon\) for \(\epsilon\in[0,1]\), then \(f\) is \(\epsilon\)-close to linear.
Lemma.
\[
\Pr_{x,y\in F_2^n}[f(x+y) = f(x) f(y)]
= \frac{1}{2} + \frac{1}{2} \sum_{\alpha\in F_2^n} \widehat{f}(\alpha)^3
\]
Proof.
First, we have
\[
\Pr_{x,y}[f(x+y) = f(x) f(y)]
= \Pr_{x,y}[ f(x)f(y)f(x+y) =1]
= \frac{1}{2} + \frac{1}{2} E[f(x)f(y)f(x+y)].
\]
We have the following facts on the Fourier expansion
\[
f(x) = \sum_{\alpha\in F_2^n} \widehat{f}(\alpha) \chi_\alpha(x),
\]
\[
\chi_\alpha(x+y) = (-1)^{\alpha(x+y)} = \chi_\alpha(x)\chi_\alpha(y),
\]
\[
\chi_\alpha(x) \chi_\gamma(x) = (-1)^{\alpha x + \gamma x} = \chi_{\alpha+\gamma}(x).
\]
Therefore, we get
\begin{eqnarray*}
E[f(x)f(y)f(x+y)]
&=& E[ \sum_{\alpha,\beta,\gamma} \widehat{f}(\alpha) \widehat{f}(\beta) \widehat{f}(\gamma) \chi_\alpha(x)\chi_\beta(y)\chi_\gamma(x+y) ] \\
&=& \sum_{\alpha,\beta,\gamma} \widehat{f}(\alpha) \widehat{f}(\beta) \widehat{f}(\gamma) E[ \chi_\alpha(x)\chi_\beta(y)\chi_\gamma(x+y) ] \\
&=& \sum_{\alpha,\beta,\gamma} \widehat{f}(\alpha) \widehat{f}(\beta) \widehat{f}(\gamma) E[ \chi_{\alpha+\gamma}(x)\chi_{\beta+\gamma}(y) ] \\
&=& \sum_{\alpha,\beta,\gamma} \widehat{f}(\alpha) \widehat{f}(\beta) \widehat{f}(\gamma) E[ \chi_{\alpha+\gamma}(x)] E[\chi_{\beta+\gamma}(y) ] \\
\end{eqnarray*}
Since \(E_x[\chi_\alpha(x)]\) is 0 if \(\alpha \neq 0\) and 1 otherwise, each item in the summation above is non-zero if and only if \(\alpha = \beta=\gamma\). Therefore,
\[
E[f(x)f(y)f(x+y)] = \sum_{\alpha } \widehat{f}(\alpha)^3
\]
An alternative way to show this is using convolution.
\begin{eqnarray*}
E[f(x)f(y)f(x+y)]
&=& E_x[f(x) E_y[ f(y)f(x+y) ] ] \\
&=& E_x[f(x) (f*f)(x) ] ] \\
&=& \langle f, f*f \rangle \\
&=& 2^n \cdot \langle \widehat{f}, \widehat{f*f} \rangle \\
&=& 2^n \cdot \langle \widehat{f}, \widehat{f}^2 \rangle \\
&=& \sum_{\alpha } \widehat{f}(\alpha)^3.
\end{eqnarray*}
\(\square\)
Then we are ready to prove the Theorem. Since \(\sum_{\alpha} \widehat{f}(\alpha)^2 = 1\),
\[
\sum_{\alpha} \widehat{f}(\alpha)^3
\leq \max_{\alpha} \widehat{f}(\alpha) \cdot \sum_{\alpha} \widehat{f}(\alpha)^2
= \max_{\alpha} \widehat{\alpha}(S)
\]
The condition that \(\Pr_{x,y}[f(x+y) = f(x) f(y)] \geq 1- \epsilon\) implies \(\max_{\alpha} \widehat{f}(\alpha) \geq 1-2\epsilon\). Since \(\widehat{f}(\alpha) = \langle f, \chi_\alpha\rangle\), we get that there exists some \(\alpha\) such that \(\langle f, \chi_\alpha\rangle \geq 1-2\epsilon\), and then \(f\) is \(\epsilon\)-close to linear.
Property Testing
A property of boolean functions is a collection of boolean functions. A property \(\mathcal{P}\) is locally testable if there is a randomized algorithm such that
- if \(f\in \mathcal{P}\), then accept;
- if \(f\) is \(\epsilon\)-far from \(\mathcal{P}\), then reject with probability \(1-\Omega(\epsilon)\).
A property \(\mathcal{P}\) is testable with \(q(\epsilon)\) queries if there is a randomized algorithm such that
- if \(f\in \mathcal{P}\), then accept with probability at least \(2/3\);
- if \(f\) is \(\epsilon\)-far from \(\mathcal{P}\), then reject with probability at least \(2/3\).
Linearity is locally testable, and testable with \(O(1/\epsilon)\) queries.