Back to Boolean Function Analysis
Back to notes

BLR Linearity Testing

80%

Given boolean function $f:\Bit^n\rightarrow\Bit$, define the following 3-query test:

• Sample $\bx,\by\in\Bit^n$ uniformaly and independently.
• If $f(\bx)\cdot f(\by)=f(\bx\circ\by)$, then accept. Otherwise, reject. Note that the multiplication here correspond to the addition in $\mathbb{F}_2$ and $\circ$ is the coordinate-wise multiplication.

The BLR linearity test above has the following properties:

• (completeness) If $f$ is linear, then the test always accept.
• (soundness) If the test accepts $f$ with probability greater than $1-\epsilon$, then $f$ is $\epsilon$-close to linear.

Before we formally prove the theorem, let’s recall some useful facts about linear function and choosing $\Bit$ as our domain.

• $f$ is a linear function iff $\exists S\subseteq[n]$ such that $f=\chi_S$.
• $f$ is $\epsilon$-close to linear iff $\max_{S\subseteq[n]}\widehat{f}(S)\geq1-2\epsilon$
• $f(\bx)+f(\by)=f(\bx+\by)$ iff $f(\bx)f(\by)f(\bx+\by)=1$
• (completeness)

This is the easy direction. As the test is basically the definition of linearity, a linear function $f$ will always pass the test.

• (soundness)

Suppose the test accepts $f$ with probability greater than $1-\epsilon$. Observe that

\begin{align} \mathbb{P}[f\text{ being accepted}] &= \frac{1}{2}+\frac{1}{2}\mathbb{E}[f(\bx)f(\by)f(\bx\circ\by)]\\
(\because\text{def. of convolution + independence of }\bx,\by) &= \frac{1}{2}+\frac{1}{2}\mathbb{E}[f(\bx)f\star f(\bx)]\\
(\because\text{Parseval’s equality})&= \frac{1}{2}+\frac{1}{2}\sum_{S\subseteq[n]}\widehat{f}(S)\widehat{f\star f}(S)\\
(\because\text{property of convolution})&= \frac{1}{2}+\frac{1}{2}\sum_{S\subseteq[n]}\widehat{f}(S)^3\\
(\because\text{Parseval’s equality and the range is }\Bit)&\leq\frac{1}{2}+\frac{1}{2}\max_{S\subseteq[n]}\widehat{f}(S). \end{align}

As the acceptance probability is at least $1-\epsilon$, we have $1-2\epsilon\leq\max_{S\subseteq[n]}\widehat{f}(S)$, i.e., $f$ is $\epsilon$-close to linear.