{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T18:22:58Z","timestamp":1648578178010},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,6,20]],"date-time":"2015-06-20T00:00:00Z","timestamp":1434758400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,7]]},"DOI":"10.1007\/s00224-015-9639-z","type":"journal-article","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T01:54:51Z","timestamp":1434678891000},"page":"99-111","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness"],"prefix":"10.1007","volume":"59","author":[{"given":"Sheela","family":"Devadas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"9639_CR1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex. 1, 3\u201340 (1991)","journal-title":"Comput. Complex."},{"issue":"6","key":"9639_CR2","doi-asserted-by":"crossref","first-page":"1781","DOI":"10.1109\/18.556674","volume":"42","author":"M Bellare","year":"1996","unstructured":"Bellare, M., Coppersmith, D., H\u00e5stad, J., Kiwi, M., Sudan, M.: Linearity testing over characteristic two. IEEE Trans. Inf. Theory 42(6), 1781\u20131795 (1996)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9639_CR3","doi-asserted-by":"crossref","unstructured":"Bellare, M., Goldwasser, S., Lund, C., Russell, A.: Efficient probabilistically checkable proofs and applications to approximations. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, pp 294\u2013304 (1993)","DOI":"10.1145\/167088.167174"},{"key":"9639_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Sudan, M., Vadhan, S., Wigderson, A.: Randomness-efficient low degree tests and short pcps via epsilon-biased sets. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on the Theory of Computing, pp 612\u2013621 (2003)","DOI":"10.1145\/780542.780631"},{"key":"9639_CR5","first-page":"549","volume":"47","author":"M Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. JCSS 47, 549\u2013595 (1993)","journal-title":"JCSS"},{"issue":"1","key":"9639_CR6","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1145\/200836.200880","volume":"42","author":"M Blum","year":"1995","unstructured":"Blum, M., Kannan, S.: Designing programs that check their work. J. ACM 42(1), 269\u2013291 (1995)","journal-title":"J. ACM"},{"issue":"3","key":"9639_CR7","doi-asserted-by":"crossref","first-page":"979","DOI":"10.1137\/070711761","volume":"39","author":"M F\u00fcrer","year":"2009","unstructured":"F\u00fcrer, M.: Faster integer multiplication. SIAM J. Comput. 39(3), 979\u20131005 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9639_CR8","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. JACM 45(4), 653\u2013750 (1998)","journal-title":"JACM"},{"issue":"2","key":"9639_CR9","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1002\/rsa.10068","volume":"22","author":"J Hastad","year":"2003","unstructured":"Hastad, J., Wigderson, A.: Simple analysis of graph tests for linearity and pcp. Random Struct. Algo. 22(2), 139\u2013160 (2003)","journal-title":"Random Struct. Algo."},{"key":"9639_CR10","unstructured":"Kaufman, T., Litsyn, S., Xie, N.: Breaking the \ud835\udf16-soundness bound of the linearity test over gf(2). Private Communications (2006)"},{"key":"9639_CR11","unstructured":"Kiwi, M.: Probabilistically Checkable Proofs and the testing of Hadamard-like codes. PhD thesis, Massachusetts Institute of Technology (1996)"},{"issue":"5","key":"9639_CR12","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1007\/s00224-004-1125-y","volume":"38","author":"F Magniez","year":"2005","unstructured":"Magniez, F.: Multi-linearity self-testing with relative error. Theory Comput. Syst. 38(5), 573\u2013591 (2005)","journal-title":"Theory Comput. Syst."},{"key":"9639_CR13","unstructured":"Rubinfeld, R., Sudan, M.: Self-testing polynomial functions efficiently and over rational domains. In: Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp 23\u201332 (1992)"},{"issue":"2","key":"9639_CR14","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM J. Comput. 25(2), 252\u2013271 (1996)","journal-title":"SIAM J. Comput."},{"key":"9639_CR15","doi-asserted-by":"crossref","unstructured":"Samorodnitsky, A., Trevisan, L.: A pcp characterization of np with optimal amortized query complexity. In: stoc00, pp 191\u2013199 (2000)","DOI":"10.1145\/335305.335329"},{"key":"9639_CR16","doi-asserted-by":"crossref","unstructured":"Samorodnitsky, A., Trevisan, L.: Gowers uniformity, influence of variables, and pcps. In: stoc06, pp 11\u201320 (2006)","DOI":"10.1145\/1132516.1132519"},{"key":"9639_CR17","doi-asserted-by":"crossref","unstructured":"Shpilka, A., Wigderson, A.: Derandomizing homomorphism testing in general groups. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on the Theory of Computing, pp 427\u2013435 (2004)","DOI":"10.1145\/1007352.1007421"},{"key":"9639_CR18","doi-asserted-by":"crossref","unstructured":"Sudan, M., Trevisan, L.: Probabilistically checkable proofs with low amortized query complexity. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p 18 (1998)","DOI":"10.1109\/SFCS.1998.743425"},{"key":"9639_CR19","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Recycling queries in pcps and in linearity tests. In: Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, pp 299\u2013308 (1998)","DOI":"10.1145\/276698.276769"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9639-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-015-9639-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9639-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,27]],"date-time":"2019-08-27T05:03:20Z","timestamp":1566882200000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-015-9639-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,20]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["9639"],"URL":"https:\/\/doi.org\/10.1007\/s00224-015-9639-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,20]]}}}