2022/01/26 by Kaufman, Tali, Litsyn, Simon, Xie, Ning
#Fourier analysis #Linearity test #coding theory
paper · doi:10.4230/dagsemproc.08341.3
For Boolean functions that are epsilon-far from the set of linear functions, we study the lower bound on the rejection probability (denoted by extscrej(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 extscrej(epsilon) were obtained by Bellare, Coppersmith, Hastad, Kiwi and Sudan. They used Fourier analysis to show that extscrej(epsilon) geq e for every 0 leq epsilon leq frac12. 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 extscrej(epsilon) geq epsilon by an additive constant that depends only on epsilon: extscrej(epsilon) geq epsilon + min 1376epsilon3(1-2epsilon)12, frac14epsilon(1-2epsilon)4, for every 0 leq epsilon leq frac12. Our analysis is based on a relationship between extscrej(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.