Name
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 REJ(epsilon)) of the linearity test suggested by Blum, Luby, and Rubinfeld [J. Comput. System Sci., 47 (1993), pp. 549-595]. This problem is arguably the most fundamental and extensively studied problem in property testing of Boolean functions. The previously best bounds for REJ(epsilon) were obtained by Bellare et al. [IEEE Trans. Inform. Theory, 42 (1996), pp. 1781-1795]. They used Fourier analysis to show that REJ(epsilon) >= epsilon for every 0 <= epsilon <= 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 REJ(epsilon) >= epsilon by an additive constant that depends only on epsilon: REJ(epsilon) >= epsilon + min{1376 epsilon(3)(1-2 epsilon)(12), 1/4 epsilon(1-2 epsilon)(4)}, for every 0 <= epsilon <= 1/2. Our analysis is based on a relationship between REJ(epsilon) and the weight distribution of a coset code of the Hadamard code. We use both Fourier analysis and coding theory tools to estimate this weight distribution. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1137/080715548 | SIAM JOURNAL ON COMPUTING |
Keywords | Field | DocType |
property testing,linearity test,coding theory,Fourier analysis | Applied mathematics,Mathematical analysis,Linearity,Arithmetic,Soundness,GF(2),Mathematics | Journal |
Volume | Issue | ISSN |
39 | 5 | 0097-5397 |
Citations | PageRank | References |
9 | 0.64 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tali Kaufman | 1 | 499 | 38.33 |
| Simon N. Litsyn | 2 | 843 | 106.44 |
| Ning Xie | 3 | 142 | 7.11 |