{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T11:36:47Z","timestamp":1790422607631,"version":"4.1.0"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>Given (the table of) a function $f : \\mathbb{F}^m \\rightarrow \\mathbb{F}$ over a finite field $\\mathbb{F}$, a low degree tester tests its agreement with an m-variate polynomial of total degree at most d over $\\mathbb{F}$. The tester is usually given access to an oracle $\\mathcal{A}$ providing the supposed restrictions of f to affine subspaces of constant dimension (e.g., lines, planes, etc.). The tester makes very few (probabilistic) queries to f and to $\\mathcal{A}$ (say, one query to f and one query to $\\mathcal{A}$) and decides whether to accept or reject based on the replies. We wish to minimize two parameters of the tester: its error and its size. The error bounds the probability that the tester accepts although the function is far from a low degree polynomial. The size is the number of bits required to write the oracle replies on all possible tester queries. Low degree testing is a central ingredient in most constructions of probabilistically checkable proofs (PCPs). The error of the low degree tester is related to the error of the PCP, and its size is related to the size of the PCP. We design and analyze new low degree testers that have both subconstant error $o(1)$ and almost-linear size $n^{1+o(1)}$ (where $n = \\left|\\mathbb{F}\\right|^{m}$). Previous constructions of subconstant error testers had polynomial size. These testers enabled the construction of PCPs with subconstant error, but polynomial size. Previous constructions of almost-linear size testers obtained only constant error. These testers were used to construct almost-linear size PCPs with constant error. The testers we present in this work enabled the construction of PCPs with both subconstant error and almost-linear size.<\/jats:p>","DOI":"10.1137\/060656838","type":"journal-article","created":{"date-parts":[[2008,3,29]],"date-time":"2008-03-29T03:17:28Z","timestamp":1206760648000},"page":"140-180","source":"Crossref","is-referenced-by-count":21,"title":["Sub-Constant Error Low Degree Test of Almost-Linear Size"],"prefix":"10.1137","volume":"38","author":[{"given":"Dana","family":"Moshkovitz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,3,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0025-0"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446810"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson and M. Sudan,\n                      Simple PCPs with poly-log rate and query complexity\n                      , in Proceedings of the 37th ACM Symposium on Theory of Computing, 2005, pp. 266\u2013275.","DOI":"10.1145\/1060590.1060631"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, M. Sudan, S. P. Vadhan, and A. Wigderson,\n                      Randomness-efficient low degree tests and short PCPs via epsilon-biased sets\n                      , in Proceedings of the 34th ACM Symposium on Theory of Computing, 2003, pp. 612\u2013621.","DOI":"10.1145\/780542.780631"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"I. Dinur, E. Fischer, G. Kindler, R. Raz, and S. Safra,\n                      PCP characterizations of NP: Towards a polynomially-small error-probability\n                      , in Proceedings of the 31st ACM Symposium on Theory of Computing, 1999, pp. 29\u201340.","DOI":"10.1145\/301250.301265"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"R11","unstructured":"K. Ford,\n                      The Distribution of Integers with a Divisor in a Given Interval\n                      , Technical report arXiv:math\/0401223, 2004."},{"key":"R12","unstructured":"K. Friedl and M. Sudan,\n                      Some improvements to low degree tests\n                      , in Proceedings of the 3rd Israel Symposium on Theory and Computing Systems, IEEE, New York, 1995."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/1162349.1162351"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"R. Hall and G. Tenenbaum,\n                      Divisors\n                      , Cambridge Tracts in Math. 90, Cambridge University Press, London, 1988.","DOI":"10.1017\/CBO9780511566004"},{"key":"R15","unstructured":"D. Moshkovitz and R. Raz,\n                      Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size\n                      , Technical report TR07-026, Electronic Colloquium on Computational Complexity, 2007."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"A. Polishchuk and D. A. Spielman,\n                      Nearly-linear size holographic proofs\n                      , in Proceedings of the 26th ACM Symposium on Theory of Computing, 1994, pp. 194\u2013203.","DOI":"10.1145\/195058.195132"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"R. Raz and S. Safra,\n                      A sub-constant error-probability low-degree test and a sub-constant error-probability PCP characterization of NP\n                      , in Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 475\u2013484.","DOI":"10.1145\/258533.258641"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060656838","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:22:55Z","timestamp":1787336575000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060656838"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/060656838"],"URL":"https:\/\/doi.org\/10.1137\/060656838","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}