TR07-098 Authors: Tali Kaufman, Simon Litsyn, Ning Xie

Publication: 13th October 2007 12:05

Downloads: 3681

Keywords:

For Boolean functions that are $\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted $\textsc{rej}(\epsilon)$) of the linearity test suggested by Blum, Luby and Rubinfeld. The interest in this problem is partly due to its relation to PCP constructions and hardness of approximating some

NP-hard problems. It seems that the problem of lower bounding

$\textsc{rej}(\epsilon)$ becomes more difficult as $\epsilon$

approaches $1/2$.

The previously best bounds for $\textsc{rej}(\epsilon)$ were obtained

by Bellare, Coppersmith, H{\r{a}}stad, Kiwi and Sudan. They used Fourier analysis to show that $\textsc{rej}(\epsilon) \geq \e$ for every $0 \leq

\epsilon \leq \frac{1}{2}$. They also conjectured that this bound

might not be tight for $\epsilon$'s which are close to $1/2$. In this

paper we show that this indeed is the case. Specifically, we improve

the lower bound of $\textsc{rej}(\epsilon) \geq \epsilon$ by an

additive constant that depends only on $\epsilon$:

$\textsc{rej}(\epsilon) \geq \epsilon + \min

\{1376\epsilon^{3}(1-2\epsilon)^{12},

\frac{1}{4}\epsilon(1-2\epsilon)^{4}\}$, for every $0 \leq \epsilon

\leq \frac{1}{2}$. Our analysis is based on a relationship between

$\textsc{rej}(\epsilon)$ and the weight distribution of a coset of the

Hadamard code. We use both Fourier analysis and coding theory tools to

estimate this weight distribution.