{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:27:14Z","timestamp":1787340434673,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>For Boolean functions that are $\\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted by $\\textsc{rej}(\\epsilon)$) of the linearity test suggested by Blum, Luby, and Rubinfeld [J. Comput. System Sci., 47 (1993), pp. 549\u2013595]. This problem is arguably the most fundamental and extensively studied problem in property testing of Boolean functions. The previously best bounds for $\\textsc{rej}(\\epsilon)$ were obtained by Bellare et al. [IEEE Trans. Inform. Theory, 42 (1996), pp. 1781\u20131795]. They used Fourier analysis to show that $\\textsc{rej}(\\epsilon)\\geq\\epsilon$ for every $0\\leq\\epsilon\\leq1\/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 $\\textsc{rej}(\\epsilon)\\geq\\epsilon$ by an additive constant that depends only on $\\epsilon$: $\\textsc{rej}(\\epsilon)\\geq\\epsilon+\\min\\{1376\\epsilon^{3}(1-2\\epsilon)^{12},\\frac{1}{4}\\epsilon(1-2\\epsilon)^{4}\\}$, for every $0\\leq\\epsilon\\leq1\/2$. Our analysis is based on a relationship between $\\textsc{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.<\/jats:p>","DOI":"10.1137\/080715548","type":"journal-article","created":{"date-parts":[[2010,2,3]],"date-time":"2010-02-03T18:09:38Z","timestamp":1265220578000},"page":"1988-2003","source":"Crossref","is-referenced-by-count":18,"title":["Breaking the $\\epsilon$-Soundness Bound of the Linearity Test over GF(2)"],"prefix":"10.1137","volume":"39","author":[{"given":"Tali","family":"Kaufman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simon","family":"Litsyn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ning","family":"Xie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,2,3]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron,\n                      Testing low-degree polynomials over GF\n                      (2), in Proceedings of RANDOM 2003, 2003, pp. 188\u2013199.","DOI":"10.1007\/978-3-540-45198-3_17"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1747"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1109\/18.556674"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Goldwasser, C. Lund, and A. Russell,\n                      Efficient probabilistically checkable proofs and applications to approximation\n                      , in Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993, pp. 304\u2013294.","DOI":"10.1145\/167088.167174"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"M. Bellare and M. Sudan,\n                      Improved non-approximability results\n                      , in Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, 1994, pp. 184\u2013193.","DOI":"10.1145\/195058.195129"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, M. Sudan, S. Vadhan, and A. Wigderson,\n                      Randomness-efficient low degree tests and short PCPs via epsilon-biased sets\n                      , in Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, 2003, pp. 612\u2013621.","DOI":"10.1145\/780542.780631"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"R11","first-page":"97","volume":"75","author":"Fischer E.","year":"2001","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0252-9742","issn-type":"print"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10068"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"C. S. Jutla, A. C. Patthak, A. Rudra, and D. Zuckerman,\n                      Testing low-degree polynomials over prime fields\n                      , in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 423\u2013432.","DOI":"10.1109\/FOCS.2004.64"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"T. Kaufman and S. Litsyn,\n                      Almost orthogonal linear codes are locally testable\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 317\u2013326.","DOI":"10.1109\/SFCS.2005.16"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"T. Kaufman and D. Ron,\n                      Testing polynomials over general fields\n                      , in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 413\u2013422.","DOI":"10.1109\/FOCS.2004.65"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00816-2"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1960.1057584"},{"key":"R20","unstructured":"D. Ron,\n                      Property testing (a tutorial)\n                      , in Handbook of Randomized Computing, P.M. Pardalos, S. Rajasekaran, J. Reif, and J.D.P. Rolim, eds., Kluwer Academic Publishers, Dordrecht, 2001, pp. 597\u2013649."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"R. Rubinfeld,\n                      Sublinear time algorithms\n                      , in Proceedings of the International Congress of Mathematicians (ICM), 2006, pp. 1095\u20131110.","DOI":"10.4171\/022-3\/53"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"A. Samorodnitsky,\n                      Low-degree tests at large distances\n                      , in Proceedings of the 39th Annual ACM Symposium on the Theory of Computing, 2007, pp. 506\u2013515.","DOI":"10.1145\/1250790.1250864"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"A. Samorodnitsky and L. Trevisan,\n                      A PCP characterization of NP with optimal amortized query complexity\n                      , in Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing, 2000, pp. 191\u2013199.","DOI":"10.1145\/335305.335329"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"A. Samorodnitsky and L. Trevisan,\n                      Gower uniformity, influence of variables and PCPs\n                      , in Proceedings of the 38th Annual ACM Symposium on the Theory of Computing, 2006, pp. 11\u201320.","DOI":"10.1145\/1132516.1132519"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970444658X"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"M. Sudan and L. Trevisan,\n                      Probabilistically checkable proofs with low amortized query complexity\n                      , in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 18\u201327.","DOI":"10.1109\/SFCS.1998.743425"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"L. Trevisan,\n                      Recycling queries in PCPs and linearity tests\n                      , in Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, 1998, pp. 299\u2013308.","DOI":"10.1145\/276698.276769"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080715548","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:57Z","timestamp":1787337297000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080715548"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080715548"],"URL":"https:\/\/doi.org\/10.1137\/080715548","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}