{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T16:32:39Z","timestamp":1789662759522,"version":"4.0.1"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>In this work we fill the knowledge gap concerning testing polynomials over finite fields. As previous works show, when the cardinality of the field, q, is sufficiently larger than the degree bound, d, then the number of queries sufficient for testing is polynomial or even linear in d. On the other hand, when $q=2$ then the number of queries, both sufficient and necessary, grows exponentially with d. Here we study the intermediate case where $2 &lt; q = O(d)$ and show a smooth transition between the two extremes. Specifically, let p be the characteristic of the field (so that p is prime and $q = p^s$ for some integer $s \\geq 1$). Then the number of queries performed by the test grows like $\\ell\\cdot q^{2\\ell+1}$, where $\\ell = \\big\\lceil \\frac{d+1}{q-q\/p}\\big\\rceil $. Furthermore, $q^{\\Omega(\\ell)}$ queries are necessary when $q = O(d)$. The test itself provides a unifying view of the tests for these two extremes: it considers random affine subspaces of dimension $\\ell$ and verifies that the function restricted to the selected subspaces is a polynomial of degree at most d. Viewed in the context of coding theory, our result shows that Reed\u2013Muller codes over general fields (usually referred to as generalized Reed\u2013Muller (GRM) codes) are locally testable. In the course of our analysis we provide a characterization of small\u2010weight words that span the code. Such a characterization was previously known only when the field size is a prime or is sufficiently large, in which case the minimum\u2010weight words span the code.<\/jats:p>","DOI":"10.1137\/s0097539704445615","type":"journal-article","created":{"date-parts":[[2006,11,15]],"date-time":"2006-11-15T22:46:25Z","timestamp":1163630785000},"page":"779-802","source":"Crossref","is-referenced-by-count":42,"title":["Testing Polynomials over General Fields"],"prefix":"10.1137","volume":"36","author":[{"given":"Tali","family":"Kaufman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,10,30]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.856958"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"N. Alon, M. Krivelevich, T. Kaufman, and D. Ron,\n                      Testing triangle\u2010freeness in general graphs\n                      , in Proceedings of the Seventeenth Annual ACM\u2010SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2006.","DOI":"10.1145\/1109557.1109589"},{"key":"R3","unstructured":"S. Arora,\n                      Probabilistic Checking of Proofs and the Hardness of Approximation Problems\n                      , Ph.D. thesis, UC Berkeley, Berkeley, CA, 1994."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"S. Arora and M. Sudan,\n                      Improved low\u2010degree testing and its applications\n                      , in Proceedings of the Twenty\u2010Ninth Annual ACM Symposium on the Theory of Computing, ACM, New York, 1997, pp. 485\u2013495.","DOI":"10.1145\/258533.258642"},{"key":"R5","unstructured":"E. F. Assmus, Jr., and J. D. Key,\n                      Designs and Their Codes\n                      , Cambridge Tracts in Math. 103, Cambridge University Press, Cambridge, UK, 1992."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, L. Levin, and M. Szegedy,\n                      Checking computations in polylogarithmic time\n                      , in Proceedings of the Twenty\u2010Third Annual ACM Symposium on Theory of Computing, ACM, New York, 1991, pp. 21\u201331.","DOI":"10.1145\/103418.103428"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.851735"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1109\/18.556674"},{"key":"R10","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 Twenty\u2010Fifth Annual ACM Symposium on the Theory of Computing, ACM, New York, 1993, pp. 294\u2013304.","DOI":"10.1145\/167088.167174"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"M. Bellare and M. Sudan,\n                      Improved non\u2010approximability results\n                      , in Proceedings of the Twenty\u2010Sixth Annual ACM Symposium on the Theory of Computing, ACM, New York, 1994, pp. 184\u2013193.","DOI":"10.1145\/195058.195129"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"E. Ben\u2010Sasson, O. Goldreich, P. Harsha, M. Sudan, and S. Vadhan,\n                      Robust PCPs of proximity, shorter PCPs and applications to coding\n                      , in Proceedings of the Thirty\u2010Sixth Annual ACM Symposium on the Theory of Computing, ACM, New York, 2004, pp. 1\u201310.","DOI":"10.1145\/1007352.1007361"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445445"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"E. Ben\u2010Sasson, M. Sudan, S. Vadhan, and A. Wigderson,\n                      Derandomizing low degree tests via epsilon\u2010biased spaces\n                      , in Proceedings of the Thirty\u2010Fifth Annual ACM Symposium on the Theory of Computing, ACM, New York, 2003, pp. 612\u2013621.","DOI":"10.1145\/780542.780631"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1109\/18.868484"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"I. Dinur,\n                      The PCP theorem via gap amplification\n                      , in Proceedings of the Thirty\u2010Eighth Annual ACM Symposium on the Theory of Computing, ACM, New York, 2006, pp. 241\u2013250.","DOI":"10.1145\/1132516.1132553"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"K. Friedl and M. Sudan,\n                      Some improvements to total degree tests\n                      , in Proceedings of the 3rd Annual Israel Symposium on Theory of Computing and Systems, Tel Aviv, Israel, 1995, pp. 190\u2013198; corrected version available online at http:\/\/theory.lcs.mit.edu\/\u02dcmadhu\/papers\/friedl.ps.","DOI":"10.1109\/ISTCS.1995.377032"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson,\n                      Self\u2010testing\/correcting for polynomials and for approximate functions\n                      , in Proceedings of the Twenty\u2010Third Annual ACM Symposium on Theory of Computing, ACM, New York, 1991, pp. 32\u201342.","DOI":"10.1145\/103418.103429"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050060"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"O. Goldreich and M. Sudan,\n                      Locally testable codes and PCPs of almost\u2010linear length\n                      , in Proceedings of the Forty\u2010Third Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2002, pp. 13\u201322.","DOI":"10.1109\/SFCS.2002.1181878"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"C. S. Jutla, A. C. Patthak, A. Rudra, and D. Zuckerman,\n                      Testing low\u2010degree polynomials over prime fields\n                      , in Proceedings of the Forty\u2010Fifth Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2004, pp. 423\u2013432.","DOI":"10.1109\/FOCS.2004.64"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436424"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"T. Kaufman and S. Litsyn,\n                      Almost orthogonal linear codes are locally testable\n                      , in Proceedings of the Forty\u2010Sixth Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2005, pp. 317\u2013326.","DOI":"10.1109\/SFCS.2005.16"},{"key":"R28","unstructured":"F. J. MacWilliams and N. J. A. Sloane,\n                      The Theory of Error Correcting Codes\n                      , North\u2013Holland, Amsterdam, 1977."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"A. Polishchuk and D. Spielman,\n                      Nearly\u2010linear size holographic proofs\n                      , in Proceedings of the Twenty\u2010Sixth Annual ACM Symposium on Theory of Computing, ACM, New York, 1994, pp. 194\u2013203.","DOI":"10.1145\/195058.195132"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"A. Shpilka and A. Wigderson,\n                      Derandomizing homomorphism testing in general groups\n                      , in Proceedings of the Thirty\u2010Sixth Annual ACM Symposium on Theory of Computing, ACM, New York, 2004, pp. 427\u2013435.","DOI":"10.1145\/1007352.1007421"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"M. Sudan,\n                      Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems\n                      , Lecture Notes in Comput. Sci. 1001, Springer\u2010Verlag, Berlin, 1996.","DOI":"10.1007\/3-540-60615-7"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539704445615","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:25:59Z","timestamp":1787336759000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539704445615"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/S0097539704445615"],"URL":"https:\/\/doi.org\/10.1137\/s0097539704445615","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}