乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:31:17Z","timestamp":1725517877741},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540853626"},{"type":"electronic","value":"9783540853633"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-85363-3_39","type":"book-chapter","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T15:29:28Z","timestamp":1219850968000},"page":"498-511","source":"Crossref","is-referenced-by-count":0,"title":["Breaking the \u03b5-Soundness Bound of the Linearity Test over GF(2)"],"prefix":"10.1007","author":[{"given":"Tali","family":"Kaufman","sequence":"first","affiliation":[]},{"given":"Simon","family":"Litsyn","sequence":"additional","affiliation":[]},{"given":"Ning","family":"Xie","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"39_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S., Ron, D.: Testing low-degree polynomials over GF(2). In: Proceedings of Random 2003, pp. 188\u2013199 (2003)","DOI":"10.1007\/978-3-540-45198-3_17"},{"issue":"4","key":"39_CR2","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1006\/jcss.2001.1747","volume":"62","author":"Y. Aumann","year":"2001","unstructured":"Aumann, Y., H\u00e5stad, J., Rabin, M., Sudan, M.: Linear-consistency testing. J. Comp. Sys. Sci.\u00a062(4), 589\u2013607 (2001)","journal-title":"J. Comp. Sys. Sci."},{"key":"39_CR3","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has twoprover interactive protocols. In: Computational Complexity, vol.\u00a01(1), pp. 3\u201340 (1991); Earlier version in FOCS 1990","DOI":"10.1007\/BF01200056"},{"issue":"6","key":"39_CR4","doi-asserted-by":"publisher","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 Transactions on Information Theory\u00a042(6), 1781\u20131795 (1996); Earlier version in FOCS 1995","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3","key":"39_CR5","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M. Bellare","year":"1998","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCP and non-approximability - towards tight results. SIAM J. on Comput.\u00a027(3), 804\u2013915 (1998); Earlier version in FOCS 1995","journal-title":"SIAM J. on Comput."},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"Bellare, M., Goldwasser, S., Lund, C., Russell, A.: Efficient probabilistically checkable proofs and applications to approximation. In: Proc. 25th Annual ACM Symposium on the Theory of Computing, pp. 304\u2013294 (1993)","DOI":"10.1145\/167088.167174"},{"key":"39_CR7","doi-asserted-by":"crossref","unstructured":"Bellare, M., Sudan, M.: Improved non-approximability results. In: Proc. 26th Annual ACM Symposium on the Theory of Computing, pp. 184\u2013193 (1994)","DOI":"10.1145\/195058.195129"},{"key":"39_CR8","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: Proc. 35th Annual ACM Symposium on the Theory of Computing, pp. 612\u2013621 (2003)","DOI":"10.1145\/780627.780631"},{"key":"39_CR9","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. J. Comp. Sys. Sci.\u00a047, 549\u2013595 (1993); Earlier version in STOC 1990","journal-title":"J. Comp. Sys. Sci."},{"key":"39_CR10","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Approximating clique is almost NP-complete. In: Journal of the ACM; Earlier version in FOCS 1991"},{"key":"39_CR11","first-page":"97","volume":"75","author":"E. Fischer","year":"2001","unstructured":"Fischer, E.: The art of uninformed decisions: A primer to property testing. Bulletin of the European Association for Theoretical Computer Science\u00a075, 97\u2013126 (2001)","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"39_CR12","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwaser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM\u00a045, 653\u2013750 (1998); Earlier version in FOCS 1996","journal-title":"Journal of the ACM"},{"issue":"4","key":"39_CR13","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. Journal of the ACM\u00a048(4), 798\u2013859 (2001); Earlier version in STOC 1997","journal-title":"Journal of the ACM"},{"key":"39_CR14","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1002\/rsa.10068","volume":"22","author":"J. H\u00e5stad","year":"2003","unstructured":"H\u00e5stad, J., Wigderson, A.: Simple analysis of graph tests for linearity and PCP. Random Structures and Algorithms\u00a022, 139\u2013160 (2003)","journal-title":"Random Structures and Algorithms"},{"key":"39_CR15","unstructured":"Jutla, C.S., Patthak, A.C., Rudra, A., Zuckerman, D.: Testing low-degree polynomials over prime fields. In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 423\u2013432 (2004)"},{"issue":"1-3","key":"39_CR16","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0304-3975(02)00816-2","volume":"299","author":"M. Kiwi","year":"2003","unstructured":"Kiwi, M.: Algebraic testing and weight distributions of codes. Theor. Comp. Sci.\u00a0299(1-3), 81\u2013106 (2003); Earlier version appeared as ECCC TR97-010 (1997)","journal-title":"Theor. Comp. Sci."},{"key":"39_CR17","unstructured":"Kaufman, T., Litsyn, S.: Almost orthogonal linear codes are locally testable. In: Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 317\u2013326 (2005)"},{"key":"39_CR18","unstructured":"Kaufman, T., Litsyn, S., Xie, N.: Breaking the \u03b5-soundness bound of the linearity test over GF(2). Technical Report TR07-098, Electronic Colloquium on Computational Complexity (2007)"},{"key":"39_CR19","unstructured":"Kaufman, T., Ron, D.: Testing polynomials over general fields. In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 413\u2013422 (2004)"},{"key":"39_CR20","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1109\/TIT.1960.1057584","volume":"6","author":"M. Plotkin","year":"1960","unstructured":"Plotkin, M.: Binary codes with specified minimum distance. IRE Transactions on Information Theory\u00a06, 445\u2013450 (1960)","journal-title":"IRE Transactions on Information Theory"},{"key":"39_CR21","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/978-1-4615-0013-1_15","volume-title":"Handbook of Randomized Computing","author":"D. Ron","year":"2001","unstructured":"Ron, D.: Property testing (a tutorial). In: Pardalos, P.M., Rajasekaran, S., Reif, J., Rolim, J.D.P. (eds.) Handbook of Randomized Computing, pp. 597\u2013649. Kluwer Academic Publishers, Dordrecht (2001)"},{"issue":"2","key":"39_CR22","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. on Comput.\u00a025(2), 252\u2013271 (1996)","journal-title":"SIAM J. on Comput."},{"key":"39_CR23","unstructured":"Rubinfeld, R.: Sublinear time algorithms. In: Proceedings of the International Congress of Mathematicians (2006)"},{"key":"39_CR24","doi-asserted-by":"crossref","unstructured":"Samorodnitsky, A.: Low-degree tests at large distances. In: Proc. 39th Annual ACM Symposium on the Theory of Computing, pp. 506\u2013515 (2007)","DOI":"10.1145\/1250790.1250864"},{"key":"39_CR25","doi-asserted-by":"crossref","unstructured":"Samorodnitsky, A., Trevisan, L.: A PCP characterization of NP with optimal amortized query complexity. In: Proc. 32nd Annual ACM Symposium on the Theory of Computing, pp. 191\u2013199 (2000)","DOI":"10.1145\/335305.335329"},{"key":"39_CR26","doi-asserted-by":"crossref","unstructured":"Samorodnitsky, A., Trevisan, L.: Gower uniformity, influence of variables and PCPs. In: Proc. 38th Annual ACM Symposium on the Theory of Computing, pp. 11\u201320 (2006)","DOI":"10.1145\/1132516.1132519"},{"key":"39_CR27","unstructured":"Sudan, M., Trevisan, L.: Probabilistically checkable proofs with low amortized query complexity. In: Proc. 39th Annual IEEE Symposium on Foundations of Computer Science, pp. 18\u201327 (1998)"},{"issue":"4","key":"39_CR28","doi-asserted-by":"publisher","first-page":"1215","DOI":"10.1137\/S009753970444658X","volume":"36","author":"A. Shpilka","year":"2006","unstructured":"Shpilka, A., Wigderson, A.: Derandomizing homomorphism testing in general groups. SIAM J. on Comput.\u00a036(4), 1215\u20131230 (2006); Earlier version in STOC 2004","journal-title":"SIAM J. on Comput."},{"key":"39_CR29","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Recycling queries in PCPs and linearity tests. In: Proc. 30th Annual ACM Symposium on the Theory of Computing, pp. 299\u2013308 (1998)","DOI":"10.1145\/276698.276769"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85363-3_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T11:34:07Z","timestamp":1558265647000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85363-3_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540853626","9783540853633"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85363-3_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}