Breaking the epsilon-Soundness Bound of the Linearity Test over Gf(2)
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 m...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2010
|
| Online Access: | http://hdl.handle.net/1721.1/58304 |
| _version_ | 1826191200937312256 |
|---|---|
| author | Kaufman-Halman, Tali Litsyn, Simon Xie, Ning |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Kaufman-Halman, Tali Litsyn, Simon Xie, Ning |
| author_sort | Kaufman-Halman, Tali |
| collection | MIT |
| description | 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)[geq]epsilon for every 0[leq]epsilon [leq]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)[geq]epsilon by an additive constant that depends only on epsilon: REJ(epsilon)[geq] epsilon+min{1376epsilon[superscript 3](1-2epsilon)[superscript 12],[frac 1 over 4epsilon(1-2epsilon[superscript 4]}, for every 0[leq]epsilon[leq]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. |
| first_indexed | 2024-09-23T08:52:29Z |
| format | Article |
| id | mit-1721.1/58304 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:52:29Z |
| publishDate | 2010 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/583042022-09-30T11:49:04Z Breaking the epsilon-Soundness Bound of the Linearity Test over Gf(2) BREAKING THE ε-SOUNDNESS BOUND OF THE LINEARITY TEST OVER GF(2) Kaufman-Halman, Tali Litsyn, Simon Xie, Ning Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Kaufman-Halman, Tali Kaufman-Halman, Tali Xie, Ning 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)[geq]epsilon for every 0[leq]epsilon [leq]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)[geq]epsilon by an additive constant that depends only on epsilon: REJ(epsilon)[geq] epsilon+min{1376epsilon[superscript 3](1-2epsilon)[superscript 12],[frac 1 over 4epsilon(1-2epsilon[superscript 4]}, for every 0[leq]epsilon[leq]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. 2010-09-03T14:48:57Z 2010-09-03T14:48:57Z 2010-02 2008-02 Article http://purl.org/eprint/type/JournalArticle 1095-7111 0097-5397 http://hdl.handle.net/1721.1/58304 Kaufman, Tali, Simon Litsyn, and Ning Xie. "Breaking the epsilon-Soundness Bound of the Linearity Test over Gf(2)." SIAM Journal of Computing (2010) Volume 39, Issue 5 : pp. 1988-2003. ©2010 Society for Industrial and Applied Mathematics. en_US http://dx.doi.org/10.1137/080715548 SIAM Journal of Computing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Kaufman-Halman, Tali Litsyn, Simon Xie, Ning Breaking the epsilon-Soundness Bound of the Linearity Test over Gf(2) |
| title | Breaking the epsilon-Soundness Bound of the Linearity Test over Gf(2) |
| title_full | Breaking the epsilon-Soundness Bound of the Linearity Test over Gf(2) |
| title_fullStr | Breaking the epsilon-Soundness Bound of the Linearity Test over Gf(2) |
| title_full_unstemmed | Breaking the epsilon-Soundness Bound of the Linearity Test over Gf(2) |
| title_short | Breaking the epsilon-Soundness Bound of the Linearity Test over Gf(2) |
| title_sort | breaking the epsilon soundness bound of the linearity test over gf 2 |
| url | http://hdl.handle.net/1721.1/58304 |
| work_keys_str_mv | AT kaufmanhalmantali breakingtheepsilonsoundnessboundofthelinearitytestovergf2 AT litsynsimon breakingtheepsilonsoundnessboundofthelinearitytestovergf2 AT xiening breakingtheepsilonsoundnessboundofthelinearitytestovergf2 AT kaufmanhalmantali breakingtheesoundnessboundofthelinearitytestovergf2 AT litsynsimon breakingtheesoundnessboundofthelinearitytestovergf2 AT xiening breakingtheesoundnessboundofthelinearitytestovergf2 |