Breaking the ε-soundness bound of the linearity test over GF(2) Conference

Kaufman, T, Litsyn, S, Xie, N. (2008). Breaking the ε-soundness bound of the linearity test over GF(2) . EURO-PAR 2011 PARALLEL PROCESSING, PT 1, 5171 LNCS 498-511. 10.1007/978-3-540-85363-3_39

cited authors

  • Kaufman, T; Litsyn, S; Xie, N

authors

abstract

  • For Boolean functions that are ε-away from the set of linear functions, we study the lower bound on the rejection probability (denoted by rej(ε)) of the linearity test suggested by Blum, Luby and Rubinfeld. This problem is one of the most extensively studied problems in property testing of Boolean functions. The previously best bounds for rej(ε) were obtained by Bellare, Coppersmith, Håstad, Kiwi and Sudan. They used Fourier analysis to show that REJ(ε) ≥ ε for every 0 ≤ ε ≤ 1/2. They also conjectured that this bound might not be tight for ε's that are close to 1/2. In this paper we show that this indeed is the case. Specifically, we improve the lower bound of REJ(ε) ≥ ε by an additive term that depends only on ε: REJ(ε)≥ ε+min {1376ε3(1 - 2ε)12, 1/4 ε (1 - 2 ε)4}, for every 0 ≤ ε ≤ 1/2. Our analysis is based on a relationship between REJ(ε) 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. © 2008 Springer-Verlag Berlin Heidelberg.

publication date

  • September 22, 2008

published in

Digital Object Identifier (DOI)

International Standard Book Number (ISBN) 10

International Standard Book Number (ISBN) 13

start page

  • 498

end page

  • 511

volume

  • 5171 LNCS