Epsilon-biased Sets and Derandomized Linearity Testing

In this post, we will show that choosing one of the vectors from a epsilon-biased set (that is pseudorandom for for statistics like bias of parity functions), the linearity test works. Constructing small epsilon biased sets reduces the size of our sample space for the randomness used in the BLR test.

$\displaystyle \hat{f}_{\chi}=\langle f, \chi\rangle = \frac{1}{\left|\mathbb{F}^{m}\right|} \sum_{x \in \mathbb{F}^{m}} f(x) \overline{\chi(x)} .$

A set ${S \subseteq \mathbb{F}^{m}}$ is called ${\varepsilon}$ -biased if all nontrivial Fourier coefficients of the characteristic function of ${S}$ are bounded by ${\varepsilon|S| /\left|\mathbb{F}^{m}\right|,}$ . That is, for ${\chi \neq 1,\left|\sum_{y \in S} \chi(y)\right| \leq \varepsilon|S| .}$

There are deterministic constructions for such sets ${S}$ of size poly ${\log |F|^m.}$

If the rejection probability ${ Pr_{x \in F^m, y \in S}( f(x) +f(y) \neq f(x+y))}$ is small, expanding it terms of Fourier transform, we get ${\delta \leq\left|\sum_{\alpha \in \mathbf{F}_{2}^{m}} \hat{F}_{\alpha}^{2} \cdot\left\langle F, \chi_{\alpha}\right\rangle_{S}\right|}$

So we have ${|\left\langle F, \chi_{\alpha}\right\rangle_{S} | >\delta}$ for some ${\alpha}$ and we are done once we show that ${\left|\hat{F}_{\alpha}\right| \geq \sqrt{\delta^{2}-\varepsilon}}.$ To do that we need to bound ${|\left\langle F, \chi_{\beta}\right\rangle_{S} | < \varepsilon+\sqrt{2 (1-\delta)}}$ for ${\beta \neq \alpha.}$ — to get this use the epsilon biased property of ${S}$ .

Another way to think of the an epsilon-biased set is in terms of expansion of Cayley graph with generating set ${S.}$ The edges are between ${x}$ and ${x+s}$ for ${s \in S}$ . The eigenvalues of the graph are given by ${\left|\sum_{y \in S} \chi(y)\right|}$ and hence the epsilon-biased property bounds the second eigenvalue of this graph- –expansion.

(EXPANDER MIXING LEMMA) The fraction of edges between any two sets is approximately the edge density of the graph.

For ${G=(V, E)}$ a connected ${d}$ -regular graph over ${n}$ vertices with normalized second eigenvalue ${\lambda}$ and any two sets ${A, B \subseteq}$ ${V}$ of densities ${a=|A| /|V|, b=|B| /|V|,}$ let ${\mathrm{e}(A, B)}$ be the number of edges ${(u, v), u \in A, v \in B}$ . Then ${\left|\frac{e(A, B)}{d n}-a b\right| \leq \lambda \sqrt{a b}}$