{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T16:10:01Z","timestamp":1747757401592,"version":"3.41.0"},"reference-count":17,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. & Syst."],"published-print":{"date-parts":[[2015]]},"DOI":"10.1587\/transinf.2014fcp0016","type":"journal-article","created":{"date-parts":[[2015,2,28]],"date-time":"2015-02-28T22:42:15Z","timestamp":1425163335000},"page":"532-540","source":"Crossref","is-referenced-by-count":0,"title":["A Fourier-Analytic Approach to List-Decoding for Sparse Random Linear Codes"],"prefix":"10.1587","volume":"E98.D","author":[{"given":"Akinori","family":"KAWACHI","sequence":"first","affiliation":[{"name":"Tokyo Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ikko","family":"YAMANE","sequence":"additional","affiliation":[{"name":"Tokyo Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"doi-asserted-by":"crossref","unstructured":"[1] A. Akavia, S. Goldwasser, and S. Safra, \u201cProving hard-core predicates using list decoding,\u201d Proc. 44th IEEE Symposium on Foundations of Computer Science, pp.146-157, 2003.","key":"1","DOI":"10.1109\/SFCS.2003.1238189"},{"doi-asserted-by":"crossref","unstructured":"[2] Z. Brakerski, A. Langlois, C. Peikert, O. Regev, and D. Stehl\u00e9, \u201cClassical hardness of learning with errors,\u201d Proc. 45th Annual ACM Symposium on Theory of Computing, pp.575-584, 2013.","key":"2","DOI":"10.1145\/2488608.2488680"},{"doi-asserted-by":"crossref","unstructured":"[3] E.R. Berlekamp, R.J. McEliece, and H.C.A. van Tilborg, \u201cOn the inherent intractability of certain coding problems,\u201d IEEE Trans. Inf. Theory, vol.24, pp.384-386, 1978.","key":"3","DOI":"10.1109\/TIT.1978.1055873"},{"unstructured":"[4] P. Elias, \u201cList decoding for noisy channels,\u201d 1957.","key":"4"},{"doi-asserted-by":"crossref","unstructured":"[5] V. Guruswami, J. H\u00e5stad, and S. Kopparty, \u201cOn the list-decodability of random linear codes,\u201d IEEE Trans. Inf. Theory, vol.57, no.2, pp.718-725, 2011.","key":"5","DOI":"10.1109\/TIT.2010.2095170"},{"doi-asserted-by":"crossref","unstructured":"[6] O. Goldreich and L.A. Levin, \u201cA hard-core predicate for all one-way functions,\u201d STOC '89, pp.25-32, 1989.","key":"6","DOI":"10.1145\/73007.73010"},{"unstructured":"[7] V. Guruswami, \u201cList decoding of error-correcting codes,\u201d LNCS 3238, 2002. Winning Thesis of the 2002 ACM Doctoral Dissertation Competition.","key":"7"},{"doi-asserted-by":"crossref","unstructured":"[8] V. Guruswami, \u201cList decoding of binary codes-A brief survey of some recent results,\u201d 2nd International Workshop on Coding and Cryptography, pp.97-106, 2009.","key":"8","DOI":"10.1007\/978-3-642-01877-0_10"},{"doi-asserted-by":"crossref","unstructured":"[9] E. Kushilevitz and Y. Mansour, \u201cLearning decision trees using the fourier spectrum,\u201d SIAM J. Comput., vol.22, no.6, pp.1331-1348, 1993.","key":"9","DOI":"10.1137\/0222080"},{"doi-asserted-by":"crossref","unstructured":"[10] T. Kaufman and M. Sudan, \u201cSparse random linear codes are locally decodable and testable,\u201d FOCS '07, pp.590-600, 2007.","key":"10","DOI":"10.1109\/FOCS.2007.8"},{"doi-asserted-by":"crossref","unstructured":"[11] S. Kopparty and S. Saraf, \u201cLocal list-decoding and testing of random linear codes from high error,\u201d SIAM J. Comput., vol.42, no.3, pp.1302-1326, 2013.","key":"11","DOI":"10.1137\/100811945"},{"doi-asserted-by":"crossref","unstructured":"[12] O. Regev, \u201cImproved inapproximability of lattice and coding problems with preprocessing,\u201d IEEE Trans. Inf. Theory, vol.50, no.9, pp.2031-2037, 2004.","key":"12","DOI":"10.1109\/TIT.2004.833350"},{"doi-asserted-by":"crossref","unstructured":"[13] O. Regev, \u201cOn lattices, learning with errors, random linear codes, and cryptography,\u201d J. ACM, vol.56, no.6, article 34, pp.1-40, 2009.","key":"13","DOI":"10.1145\/1568318.1568324"},{"doi-asserted-by":"crossref","unstructured":"[14] O. Regev, \u201cThe learning with errors problem,\u201d Proc. 25th Annual IEEE Conference on Computational Complexity, pp.191-204, 2010.","key":"14","DOI":"10.1109\/CCC.2010.26"},{"doi-asserted-by":"crossref","unstructured":"[15] M. Sudan, \u201cList decoding: Algorithms and applications,\u201d in Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics, pp.25-41, Springer Berlin Heidelberg, 2000.","key":"15","DOI":"10.1007\/3-540-44929-9_3"},{"doi-asserted-by":"crossref","unstructured":"[16] S. Vadhan, \u201cThe unified theory of pseudorandomness,\u201d SIGACT News, vol.38, no.3, pp.39-54, 2007.","key":"16","DOI":"10.1145\/1324215.1324225"},{"unstructured":"[17] J.M. Wozencraft, \u201cList decoding,\u201d Quarterly Progress Report, vol.48, pp.90-95, 1958. Research Laboratory of Electronics, MIT.","key":"17"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E98.D\/3\/E98.D_2014FCP0016\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T15:28:14Z","timestamp":1747754894000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E98.D\/3\/E98.D_2014FCP0016\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2014fcp0016","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"type":"print","value":"0916-8532"},{"type":"electronic","value":"1745-1361"}],"subject":[],"published":{"date-parts":[[2015]]}}}