{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:19:22Z","timestamp":1725567562184},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642163661"},{"type":"electronic","value":"9783642163678"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16367-8_26","type":"book-chapter","created":{"date-parts":[[2010,10,7]],"date-time":"2010-10-07T15:25:55Z","timestamp":1286465155000},"page":"320-333","source":"Crossref","is-referenced-by-count":0,"title":["Some Recent Results on Local Testing of Sparse Linear Codes"],"prefix":"10.1007","author":[{"given":"Swastik","family":"Kopparty","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shubhangi","family":"Saraf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"26_CR1","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s00493-003-0025-0","volume":"23","author":"S. Arora","year":"2003","unstructured":"Arora, S., Sudan, M.: Improved low degree testing and its applications. Combinatorica\u00a023(3), 365\u2013426 (2003)","journal-title":"Combinatorica"},{"issue":"6","key":"26_CR2","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)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"2","key":"26_CR3","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0304-3975(01)00403-0","volume":"288","author":"N.H. Bshouty","year":"2002","unstructured":"Bshouty, N.H., Eiron, N., Kushilevitz, E.: PAC learning with nasty noise. Theor. Comput. Sci.\u00a0288(2), 255\u2013275 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"26_CR4","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1145\/792538.792543","volume":"50","author":"A. Blum","year":"2003","unstructured":"Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM\u00a050(4), 506\u2013519 (2003)","journal-title":"J. ACM"},{"issue":"3","key":"26_CR5","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. Journal of Computer and System Sciences\u00a047(3), 549\u2013595 (1993)","journal-title":"Journal of Computer and System Sciences"},{"key":"26_CR6","first-page":"613","volume-title":"FOCS","author":"I. Dinur","year":"2008","unstructured":"Dinur, I., Goldenberg, E.: Locally testing direct product in the low error range. In: FOCS, pp. 613\u2013622. IEEE Computer Society, Los Alamitos (2008)"},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"Feldman, V., Gopalan, P., Khot, S., Ponnuswami, A.K.: New results for learning noisy parities and halfspaces. In: FOCS, pp. 563\u2013574 (2006)","DOI":"10.1109\/FOCS.2006.51"},{"issue":"4","key":"26_CR8","doi-asserted-by":"publisher","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. J. ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Klivans, A.R., Zuckerman, D.: List-decoding reed-muller codes over small fields. In: Ladner and Dwork [LD08], pp. 265\u2013274","DOI":"10.1145\/1374376.1374417"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Levin, L.: A hard-core predicate for all one-way functions. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 25\u201332 (May 1989)","DOI":"10.1145\/73007.73010"},{"issue":"4","key":"26_CR11","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1137\/S0895480198344540","volume":"13","author":"O. Goldreich","year":"2000","unstructured":"Goldreich, O., Rubinfeld, R., Sudan, M.: Learning polynomials with queries: The highly noisy case. SIAM Journal on Discrete Mathematics\u00a013(4), 535\u2013570 (2000)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Jaiswal, R., Kabanets, V., Wigderson, A.: Uniform direct product theorems: simplified, optimized, and derandomized. In: Ladner, Dwork (eds.) [LD08], pp. 579\u2013588","DOI":"10.1145\/1374376.1374460"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Kabanets, V., Wigderson, A.: New direct-product testers and 2-query pcps. In: STOC, pp. 131\u2013140 (2009)","DOI":"10.1145\/1536414.1536435"},{"key":"26_CR14","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P\u2009=\u2009BPP if E requires exponential circuits: Derandomizing the XOR Lemma. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 220\u2013229 (May 1997)","DOI":"10.1145\/258533.258590"},{"issue":"3","key":"26_CR15","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1109\/18.382026","volume":"41","author":"I. Krasikov","year":"1995","unstructured":"Krasikov, I., Litsyn, S.: On spectra of BCH codes. IEEE Transactions on Information Theory\u00a041(3), 786\u2013788 (1995)","journal-title":"IEEE Transactions on Information Theory"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"Kaufman, T., Litsyn, S.: Almost orthogonal linear codes are locally testable. In: Proceedings of the Forty-sixth Annual Symposium on Foundations of Computer Science, pp. 317\u2013326 (2005)","DOI":"10.1109\/SFCS.2005.16"},{"key":"26_CR17","first-page":"590","volume-title":"FOCS","author":"T. Kaufman","year":"2007","unstructured":"Kaufman, T., Sudan, M.: Sparse random linear codes are locally decodable and testable. In: FOCS, pp. 590\u2013600. IEEE Computer Society, Los Alamitos (2007)"},{"key":"26_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1007\/978-3-642-03685-9_45","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S. Kopparty","year":"2009","unstructured":"Kopparty, S., Saraf, S.: Tolerant linearity testing and locally testable codes. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX-RANDOM 2009. LNCS, vol.\u00a05687, pp. 601\u2013614. Springer, Heidelberg (2009)"},{"volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing","year":"2008","key":"26_CR19","unstructured":"Ladner, R.E., Dwork, C. (eds.): Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, 2008, May 17-20. ACM, New York (2008)"},{"key":"26_CR20","unstructured":"Litsyn, S.: Personal Communication (2009)"},{"key":"26_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/11538462_32","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"V. Lyubashevsky","year":"2005","unstructured":"Lyubashevsky, V.: The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 378\u2013389. Springer, Heidelberg (2005)"},{"key":"26_CR22","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1145\/1132516.1132520","volume-title":"STOC","author":"D. Moshkovitz","year":"2006","unstructured":"Moshkovitz, D., Raz, R.: Sub-constant error low degree test of almost-linear size. In: Kleinberg, J.M. (ed.) STOC, pp. 21\u201330. ACM, New York (2006)"},{"issue":"6","key":"26_CR23","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1016\/j.jcss.2006.03.002","volume":"72","author":"M. Parnas","year":"2006","unstructured":"Parnas, M., Ron, D., Rubinfeld, R.: Tolerant property testing and distance approximation. J. Comput. Syst. Sci.\u00a072(6), 1012\u20131042 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"26_CR24","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 Journal on Computing\u00a025(2), 252\u2013271 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"26_CR25","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1145\/258533.258641","volume-title":"Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing","author":"R. Raz","year":"1997","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 475\u2013484. ACM Press, New York (1997)"},{"key":"26_CR26","doi-asserted-by":"crossref","unstructured":"Samorodnitsky, A.: Low-degree tests at large distances. In: STOC, pp. 506\u2013515 (2007)","DOI":"10.1145\/1250790.1250864"},{"key":"26_CR27","doi-asserted-by":"crossref","unstructured":"Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR lemma. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pp. 537\u2013546 (1999)","DOI":"10.1109\/CCC.1999.766253"},{"key":"26_CR28","unstructured":"Sudan, M.: Personal Communication (2009)"}],"container-title":["Lecture Notes in Computer Science","Property Testing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16367-8_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,3]],"date-time":"2023-06-03T18:22:02Z","timestamp":1685816522000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16367-8_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642163661","9783642163678"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16367-8_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}