{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:38Z","timestamp":1787323538297,"version":"build-2736575974"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-17-1-2429"],"award-info":[{"award-number":["N00014-17-1-2429"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1524246"],"award-info":[{"award-number":["CCF-1524246"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1524246"],"award-info":[{"award-number":["CCF-1524246"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1552097"],"award-info":[{"award-number":["CCF-1552097"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>We study the bias of random bounded-degree polynomials over odd prime fields and show that, with probability exponentially close to 1, $n$-variate polynomials of degree $d$ over $\\mathbb{F}_p$ have bias at most $p^{-\\Omega(n\/d)}$. This also yields an exponential tail bound on the weight distribution of Reed--Muller codes over odd prime fields. These results generalize bounds of Ben-Eliezer, Hod, and Lovett [ Comput. Complexity, 21 (2012), pp. 63--81] who proved similar results over $\\mathbb{F}_2$. Our bounds are based on an extremal property of the rank of sub-matrices of the generator matrices of Reed--Muller codes over odd prime fields that generalizes a property shown by Keevash and Sudakov [ SIAM J. Discrete Math., 18 (2005), pp. 713--727] for the case of $\\mathbb{F}_2$. Our tail bounds on the bias can be used to derive exponential lower bounds on the time for space-bounded learning of bounded-degree polynomials from their evaluations over odd prime fields.<\/jats:p>","DOI":"10.1137\/18m1215104","type":"journal-article","created":{"date-parts":[[2020,6,3]],"date-time":"2020-06-03T14:06:43Z","timestamp":1591193203000},"page":"1232-1247","source":"Crossref","is-referenced-by-count":2,"title":["On the Bias of Reed--Muller Codes over Odd Prime Fields"],"prefix":"10.1137","volume":"34","author":[{"given":"Paul","family":"Beame","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shayan Oveis","family":"Gharan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xin","family":"Yang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,6,3]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2462817"},{"key":"atypb2","unstructured":"P. Beame, S. Oveis Gharan, and X. Yang,\n                      On the Bias of Reed-Muller Codes over Odd Prime Fields\n                      , preprint,https:\/\/arxiv.org\/abs\/1806.06973v1, 2018."},{"key":"atypb3","unstructured":"P. Beame, S. Oveis Gharan, and X. Yang,\n                      Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials\n                      , Technical report TR18-114, Electronic Colloquium on Computational Complexity, Trier, Germany, 2018."},{"key":"atypb4","unstructured":"P. Beame, S. Oveis Gharan, and X. Yang,\n                      Time-space tradeoffs for learning finite functions from random evaluations, with applications to polynomials\n                      , in Proceedings of the 31st Conference on Learning Theory, COLT 2018, PMLR, 2018."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ffa.2018.01.006"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0020-6"},{"key":"atypb7","unstructured":"A. Bhowmick and S. Lovett,\n                      Bias vs Structure of Polynomials in Large Fields, and Applications in Effective Algebraic Geometry and Coding Theory\n                      , CoRR, abs\/1506.02047, preprint,http:\/\/arxiv.org\/abs\/1506.02047, 2015."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2822686"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"L. E. Dickson,\n                      Linear Groups with an Exposition of the Galois Field Theory\n                      , B. G. Trubner, Leipzig, 1901.","DOI":"10.5962\/bhl.title.22174"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"S. Garg, R. Raz, and A. Tal,\n                      Extractor-based time-space lower bounds for learning\n                      , in Proceedings of the 50th Annual ACM Symposium on Theory of Computing, STOC, ACM, New York, 2018.","DOI":"10.1145\/3188745.3188962"},{"key":"atypb11","first-page":"265","author":"Gopalan P.","year":"2008","journal-title":"New York"},{"key":"atypb12","unstructured":"B. Green and T. Tao,\n                      The Distribution of Polynomials over Finite Fields, with Applications to the Gowers Norms\n                      , preprint,https:\/\/arxiv.org\/abs\/0711.3191, 2007."},{"key":"atypb13","first-page":"331","volume":"2010","author":"Haramaty E.","year":"2010","journal-title":"New York"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1109\/18.651015"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1970.1054545"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(76)90355-7"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2184841"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103434634"},{"key":"atypb19","unstructured":"R. J. McEliece,\n                      Linear Recurring Sequences over Finite Fields\n                      , Ph.D. thesis, California Institute of Technology, Pasadena, CA, 1967."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1109\/IREPGELC.1954.6499441"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(00)00124-5"},{"key":"atypb22","unstructured":"I. S. Reed,\n                      A Class of Multiple-Error-Correcting Codes and the Decoding Scheme\n                      , Technical report, Massachusetts Institute of Technology, Cambridge, MA, 1953."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1970.1054553"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1215104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:08:19Z","timestamp":1787321299000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1215104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/18M1215104"],"URL":"https:\/\/doi.org\/10.1137\/18m1215104","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}