Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-098 | 2nd October 2007 00:00

Breaking the \epsilon-Soundness Bound of the Linearity Test over GF(2)

RSS-Feed




TR07-098
Authors: Tali Kaufman, Simon Litsyn, Ning Xie
Publication: 13th October 2007 12:05
Downloads: 3996
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint