{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T05:22:01Z","timestamp":1772083321445,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,12,19]],"date-time":"2016-12-19T00:00:00Z","timestamp":1482105600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2017,9]]},"DOI":"10.1007\/s00037-016-0149-4","type":"journal-article","created":{"date-parts":[[2016,12,19]],"date-time":"2016-12-19T09:21:58Z","timestamp":1482139318000},"page":"531-582","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Low-degree test with polynomially small error"],"prefix":"10.1007","volume":"26","author":[{"given":"Dana","family":"Moshkovitz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,12,19]]},"reference":[{"key":"149_CR1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1109\/18.119713","volume":"38","author":"N. Alon","year":"1992","unstructured":"Alon N., Bruck J., Naor J., Naor M., Roth R. (1992) Construction of asymptotically good, low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory 38: 509\u2013516","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3","key":"149_CR2","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora S., Lund C., Motwani R., Sudan M., Szegedy M. (1998) Proof verification and the hardness of approximation problems. Journal of the ACM 45(3): 501\u2013555","journal-title":"Journal of the ACM"},{"issue":"1","key":"149_CR3","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora S., Safra S. (1998) Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM 45(1): 70\u2013122","journal-title":"Journal of the ACM"},{"issue":"3","key":"149_CR4","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s00493-003-0025-0","volume":"23","author":"S. Arora","year":"2003","unstructured":"Arora S., Sudan M. (2003) Improved low-degree testing and its Applications. Combinatorica 23(3): 365\u2013426","journal-title":"Combinatorica"},{"key":"149_CR5","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, L. A. Levin & M. Szegedy (1991a). Checking computations in polylogarithmic time. In Proc. 23rd ACM Symp. on Theory of Computing, 21\u201332.","DOI":"10.1145\/103418.103428"},{"key":"149_CR6","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow & C. Lund (1991b). Nondeterministic Exponential Time Has Two-Prover Interactive Protocols. Computational Complexity 1, 3\u201340","DOI":"10.1007\/BF01200056"},{"key":"149_CR7","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Goldwasser, C. Lund & A. Russell (1993). Efficient probabilistically checkable proofs and applications to approximations. In Proc. 25th ACM Symp. on Theory of Computing, 294\u2013304.","DOI":"10.1145\/167088.167174"},{"issue":"4","key":"149_CR8","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1137\/S0097539705446810","volume":"36","author":"E. Ben-Sasson","year":"2006","unstructured":"Ben-Sasson E., Goldreich O., Harsha P., Sudan M., Vadhan S. (2006) Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM Journal on Computing 36(4): 889\u2013974","journal-title":"SIAM Journal on Computing"},{"key":"149_CR9","unstructured":"E. Ben-Sasson, M. Sudan, S. P. Vadhan & A. Wigderson (2003). Randomness-efficient low degree tests and short PCPs via epsilonbiased sets. In Proc. 34th ACM Symp. on Theory of Computing, 612\u2013621."},{"key":"149_CR10","doi-asserted-by":"crossref","unstructured":"M. Braverman & A. Garg (2015). Small Value Parallel Repetition for General Games. In Proc. 48th ACM Symp. on Theory of Computing, 335\u2013340.","DOI":"10.1145\/2746539.2746565"},{"key":"149_CR11","unstructured":"M. R. Capalbo, O. Reingold, S. P. Vadhan & A. Wigderson (2002). Randomness Conductors and Constant-Degree Lossless Expanders. In Proc. 34th ACM Symp. on Theory of Computing, 659\u2013668."},{"issue":"3","key":"149_CR12","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/s00037-011-0014-4","volume":"20","author":"I. Dinur","year":"2011","unstructured":"Dinur I., Fischer E., Kindler G., Raz R., Safra S. (2011) PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability. Computational Complexity 20(3): 413\u2013504","journal-title":"Computational Complexity"},{"key":"149_CR13","doi-asserted-by":"crossref","unstructured":"I. Dinur & E. Goldenberg (2008). Locally Testing Direct Product in the Low Error Range. In Proc. 49th IEEE Symp. on Foundations of Computer Science, 613\u2013622.","DOI":"10.1109\/FOCS.2008.26"},{"key":"149_CR14","doi-asserted-by":"crossref","unstructured":"I. Dinur & P. Harsha (2009). Composition of Low-Error 2-Query PCPs Using Decodable PCPs. In Proc. 50th IEEE Symp. on Foundations of Computer Science, 472\u2013481.","DOI":"10.1109\/FOCS.2009.8"},{"issue":"4","key":"149_CR15","doi-asserted-by":"crossref","first-page":"975","DOI":"10.1137\/S0097539705446962","volume":"36","author":"I. Dinur","year":"2006","unstructured":"Dinur I., Reingold O. (2006) Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem. SIAM Journal on Computing 36(4): 975\u20131024","journal-title":"SIAM Journal on Computing"},{"key":"149_CR16","doi-asserted-by":"crossref","unstructured":"I. Dinur & D. Steurer (2014a). Analytical Approach to Parallel Repetition. In Proc. 47th ACM Symp. on Theory of Computing, 624\u2013633.","DOI":"10.1145\/2591796.2591884"},{"key":"149_CR17","doi-asserted-by":"crossref","unstructured":"I. Dinur & D. Steurer (2014b). Direct Product Testing. In Computational Complexity Conference, 188\u2013196.","DOI":"10.1109\/CCC.2014.27"},{"key":"149_CR18","doi-asserted-by":"crossref","unstructured":"U. Feige & J. Kilian (1995). Impossibility results for recycling random bits in two-prover proof systems. In Proc. 27th ACM Symp. on Theory of Computing, 457\u2013468.","DOI":"10.1145\/225058.225183"},{"key":"149_CR19","doi-asserted-by":"crossref","unstructured":"P. Gemmell, R. J. Lipton, R. Rubinfeld, M. Sudan & A. Wigderson (1991). Self-Testing\/Correcting for Polynomials and for Approximate Functions. In Proc. 23rd ACM Symp. on Theory of Computing, 32\u201342.","DOI":"10.1145\/103418.103429"},{"issue":"4","key":"149_CR20","doi-asserted-by":"crossref","first-page":"1132","DOI":"10.1137\/S0097539797315744","volume":"29","author":"O. Goldreich","year":"2000","unstructured":"Goldreich O., Safra S. (2000) A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem. SIAM J. Comput. 29(4): 1132\u20131154","journal-title":"SIAM J. Comput."},{"issue":"6","key":"149_CR21","doi-asserted-by":"crossref","first-page":"1722","DOI":"10.1137\/09077299X","volume":"41","author":"R. Impagliazzo","year":"2012","unstructured":"Impagliazzo R., Kabanets V., Wigderson A. (2012) New Direct-Product Testers and 2-Query PCPs. SIAM Journal on Computing 41(6): 1722\u20131768","journal-title":"SIAM Journal on Computing"},{"key":"149_CR22","doi-asserted-by":"crossref","unstructured":"S. M. Johnson (1962). A new upper bound for error-correcting codes. IRE Transactions on Information Theory 203\u2013207.","DOI":"10.1109\/TIT.1962.1057714"},{"key":"149_CR23","unstructured":"D. Moshkovitz (2011). Lecture notes in Probabilistically Checkable Proofs. Available on the author\u2019s webpage."},{"key":"149_CR24","unstructured":"D. Moshkovitz (2014a). An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing. Technical Report 30, ECCC."},{"key":"149_CR25","doi-asserted-by":"crossref","unstructured":"D. Moshkovitz (2014b). Parallel Repetition From Fortification. In Proc. 55th IEEE Symp. on Foundations of Computer Science, 414\u2013423.","DOI":"10.1109\/FOCS.2014.51"},{"key":"149_CR26","unstructured":"D. Moshkovitz, G. Ramnarayan & H. Yuen (2015). A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM, 42:3\u201342:29."},{"issue":"1","key":"149_CR27","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1137\/060656838","volume":"38","author":"D. Moshkovitz","year":"2008","unstructured":"Moshkovitz D., Raz R. (2008) Sub-Constant Error Low Degree Test of Almost-Linear Size. SIAM Journal on Computing 38(1): 140\u2013180","journal-title":"SIAM Journal on Computing"},{"key":"149_CR28","unstructured":"D. Moshkovitz & R. Raz (2010). Two Query PCP with Sub-Constant Error. Journal of the ACM 57(29)."},{"key":"149_CR29","doi-asserted-by":"crossref","unstructured":"R. Raz & S. Safra (1997). A Sub-Constant Error-Probability Low-Degree Test and a Sub-Constant Error-Probability PCP Characterization of NP. In Proc. 29th ACM Symp. on Theory of Computing, 475\u2013484.","DOI":"10.1145\/258533.258641"},{"issue":"1","key":"149_CR30","doi-asserted-by":"crossref","first-page":"157","DOI":"10.2307\/3062153","volume":"155","author":"O. Reingold","year":"2002","unstructured":"Reingold O., Vadhan S.P., Wigderson A. (2002) Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. Annals of Mathematics 155(1): 157\u2013187","journal-title":"Annals of Mathematics"},{"issue":"2","key":"149_CR31","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld R., Sudan M. (1996) Robust Characterizations of Polynomials with Applications to Program Testing. SIAM Journal on Computing 25(2): 252\u2013271","journal-title":"SIAM Journal on Computing"},{"key":"149_CR32","doi-asserted-by":"crossref","unstructured":"M. Szegedy (1999). Many-Valued Logics and Holographic Proofs. In Automata, Languages and Programming, 26th International Colloquium, ICALP 2007. Lecture notes in Computer Science, J. Weidermann, P. van Emde Boas & M. Nielsen, editors, 676\u2013686. Springer-Verlag.","DOI":"10.1007\/3-540-48523-6_64"},{"key":"149_CR33","first-page":"245","volume":"19","author":"A. Wigderson","year":"1993","unstructured":"Wigderson A., Zuckerman D. (1993) Expanders that Beat the Eigenvalue Bound: Explicit Construction and Applications. Combinatorica 19: 245\u2013251","journal-title":"Combinatorica"},{"issue":"4","key":"149_CR34","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z","volume":"11","author":"D. Zuckerman","year":"1997","unstructured":"Zuckerman D. (1997) Randomness-optimal oblivious sampling. Random Structures and Algorithms 11(4): 345\u2013367","journal-title":"Random Structures and Algorithms"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0149-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0149-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0149-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,16]],"date-time":"2019-09-16T18:12:54Z","timestamp":1568657574000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0149-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,19]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["149"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0149-4","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,19]]}}}