Kaufman, Tali ;
Litsyn, Simon ;
Xie, Ning
Breaking the $\epsilon$Soundness Bound of the Linearity Test over GF(2)
Abstract
For Boolean functions that are $epsilon$far from the set of linear functions,
we study the lower bound on the rejection probability (denoted by $extsc{rej}(epsilon)$) of the linearity test suggested by Blum, Luby and Rubinfeld.
This problem is arguably the most fundamental and extensively studied problem in property testing of Boolean functions.
The previously best bounds for $extsc{rej}(epsilon)$ were obtained by Bellare,
Coppersmith, H{{a}}stad, Kiwi and Sudan. They used Fourier analysis
to show that $ extsc{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 $ extsc{rej}(epsilon) geq
epsilon$ by an additive constant that depends only on $epsilon$:
$extsc{rej}(epsilon) geq epsilon + min {1376epsilon^{3}(12epsilon)^{12},
frac{1}{4}epsilon(12epsilon)^{4}}$, for every $0 leq epsilon leq frac{1}{2}$.
Our analysis is based on a relationship between $extsc{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.
BibTeX  Entry
@InProceedings{kaufman_et_al:DSP:2008:1697,
author = {Tali Kaufman and Simon Litsyn and Ning Xie},
title = {Breaking the $\epsilon$Soundness Bound of the Linearity Test over GF(2)},
booktitle = {Sublinear Algorithms },
year = {2008},
editor = {Artur Czumaj and S. Muthu Muthukrishnan and Ronitt Rubinfeld and Christian Sohler},
number = {08341},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1697},
annote = {Keywords: Linearity test, Fourier analysis, coding theory}
}
Keywords: 

Linearity test, Fourier analysis, coding theory 
Seminar: 

08341  Sublinear Algorithms

Issue date: 

2008 
Date of publication: 

25.11.2008 