{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:37Z","timestamp":1787337577084,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSF","award":["CCF 2227876"],"award-info":[{"award-number":["CCF 2227876"]}]},{"name":"NSF","award":["CAREER 2239160"],"award-info":[{"award-number":["CAREER 2239160"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>The problem of testing low-degree polynomials has received significant attention over the years due to its importance in theoretical computer science. The problem is specified by three parameters, the field size [Formula: see text], the degree [Formula: see text], and the proximity parameter [Formula: see text], and the goal is to design a test that makes as few queries as possible to a given function and distinguishes between the case the function has degree at most [Formula: see text] and the case it is [Formula: see text]-far from any degree [Formula: see text] function. We say that a test is optimal if it makes [Formula: see text] queries and rejects any function which is [Formula: see text]-far from degree [Formula: see text] with probability [Formula: see text]. The most natural tester to consider is the [Formula: see text]-flat test, wherein one picks an affine subspace [Formula: see text] of dimension [Formula: see text] (chosen appropriately) uniformly at random, and checks that [Formula: see text]. The [Formula: see text]-flat test was shown to be optimal by Bhattacharyya et\u00a0al. [ Proceedings of FOCS, 2010, pp. 488\u2013497] for [Formula: see text], and later by Haramaty, Shpilka, and Sudan [ SIAM J. Comput., 42 (2013), pp. 536\u2013562] for all prime powers [Formula: see text]. Their analyses, however, has a tower type dependency on the field size [Formula: see text] (i.e., in the hidden constant in the big [Formula: see text] notation). We improve the result of Haramaty, Shpilka, and Sudan, showing that the dependency on the field size is polynomial in [Formula: see text]. Our technique also applies in the more general setting of lifted affine invariant codes and gives the same polynomial dependency on the field size. This answers a problem raised by Haramaty, Ron-Zewi, and Sudan [ Theory Comput., 11 (2015), pp. 299\u2013338]. Our approach significantly deviates from the strategy taken in earlier works and is based on studying the structure of the collection of erroneous subspaces, i.e., subspaces [Formula: see text] such that [Formula: see text] has degree greater than [Formula: see text]. Toward this end, we observe that these sets are poorly expanding in the affine Grassmann graph and use that to establish structural results on them via global hypercontractivity. We then use this structure to perform local correction on [Formula: see text].<\/jats:p>","DOI":"10.1137\/23m1571022","type":"journal-article","created":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T18:11:36Z","timestamp":1748542296000},"page":"625-663","source":"Crossref","is-referenced-by-count":1,"title":["Improved Optimal Testing Results from Global Hypercontractivity"],"prefix":"10.1137","volume":"54","author":[{"given":"Tali","family":"Kaufman","sequence":"first","affiliation":[{"name":"Department of Computer Science, Bar-Ilan University, Ramat Gan, 5290002 Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dor","family":"Minzer","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,5,29]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.856958"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/130929394"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.2307\/1970980"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"A. Bhattacharyya, S. Kopparty, G. Schoenebeck, M. Sudan, and D. Zuckerman, Optimal testing of Reed-Muller codes, in Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010, pp. 488\u2013497.","DOI":"10.1109\/FOCS.2010.54"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.5802\/aif.357"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189634"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"I. Dinur, S. Khot, G. Kindler, D. Minzer, and M. Safra, On non-optimally expanding sets in Grassmann graphs, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 940\u2013951.","DOI":"10.1145\/3188745.3188806"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"I. Dinur, S. Khot, G. Kindler, D. Minzer, and M. Safra, Towards a proof of the 2-to-1 games conjecture? in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 376\u2013389.","DOI":"10.1145\/3188745.3188804"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"D. Ellis, G. Kindler, and N. Lifshitz, An analogue of Bonami\u2019s lemma for functions on spaces of linear maps, and 2-2 games, in Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023, pp. 656\u2013660.","DOI":"10.1145\/3564246.3585116"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-8858(02)00024-6"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70577-6"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BF03041066"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.2307\/2373688"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a012"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/120879257"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20262"},{"key":"ref18","series-title":"LIPIcs Leibniz Int. Proc. Inform. 245","first-page":"11:1","volume-title":"Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques","author":"Karliner D.","year":"2022"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445615"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"T. Kaufman and M. Sudan, Algebraic property testing: The role of invariance, in Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 403\u2013412.","DOI":"10.1145\/1374376.1374434"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.03.023"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1090\/jams\/1027"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"S. Khot, D. Minzer, and M. Safra, On independent sets, 2-to-2 games, and Grassmann graphs, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 576\u2013589.","DOI":"10.1145\/3055399.3055432"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"S. Khot, D. Minzer, and M. Safra, Pseudorandom sets in Grassmann graph have near-perfect expansion, in Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018, pp. 592\u2013601.","DOI":"10.1109\/FOCS.2018.00062"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"D. Minzer and K. Z. Zheng, Optimal testing of generalized Reed-Muller codes in fewer queries, in Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023, pp. 206\u2013233.","DOI":"10.1109\/FOCS57990.2023.00022"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2012.175.3.6"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"R. Raz and S. Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, in Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, 1997, pp. 475\u2013484.","DOI":"10.1145\/258533.258641"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a025"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1571022","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:30Z","timestamp":1787336310000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1571022"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,29]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1137\/23M1571022"],"URL":"https:\/\/doi.org\/10.1137\/23m1571022","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,29]]}}}