{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T10:34:10Z","timestamp":1761647650656,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2009,3,1]],"date-time":"2009-03-01T00:00:00Z","timestamp":1235865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0343672"],"award-info":[{"award-number":["CCF-0343672"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2009,3]]},"abstract":"<jats:p>\n            Ever since the birth of coding theory almost 60 years ago, researchers have been pursuing the elusive goal of constructing the \"best codes,\" whose encoding introduces the minimum possible redundancy for the level of noise they can correct. In this article, we survey recent progress in\n            <jats:italic>list decoding<\/jats:italic>\n            that has led to\n            <jats:italic>efficient<\/jats:italic>\n            error-correction schemes with an\n            <jats:italic>optimal<\/jats:italic>\n            amount of redundancy, even against\n            <jats:italic>worst-case errors<\/jats:italic>\n            caused by a potentially malicious channel. To correct a proportion \u03c1(say 20%) of worst-case errors, these codes only need close to a proportion \u03c1 of redundant symbols. The redundancy cannot possibly be any lower information theoretically. This new method holds the promise of correcting a factor of two more errors compared to the conventional algorithms currently in use in diverse everyday applications.\n          <\/jats:p>","DOI":"10.1145\/1467247.1467269","type":"journal-article","created":{"date-parts":[[2009,2,25]],"date-time":"2009-02-25T14:44:30Z","timestamp":1235573070000},"page":"87-95","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Error correction up to the information-theoretic limit"],"prefix":"10.1145","volume":"52","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[{"name":"University of Washington, Seattle, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Atri","family":"Rudra","sequence":"additional","affiliation":[{"name":"University at Buffalo, SUNY, Buffalo, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,3]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1970-0276200-X"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90195-2"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_2_2_5_1","volume-title":"Artin automorphisms, cyclotomic function fields, and folded list-decodable codes","author":"Guruswami V.","year":"2008","unstructured":"Guruswami , V. Artin automorphisms, cyclotomic function fields, and folded list-decodable codes , 2008 . Manuscript . Guruswami, V. Artin automorphisms, cyclotomic function fields, and folded list-decodable codes, 2008. Manuscript."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.855587"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-07-02012-1"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_40"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.911222"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.782097"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.38"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1950.tb00463.x"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2003.819332"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.29"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1960.1057586"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0439"},{"key":"e_1_2_2_18_1","first-page":"633","article-title":"Error correction of algebraic block codes","volume":"4","author":"Welch L.R.","year":"1986","unstructured":"Welch , L.R. , Berlekamp , E.R . Error correction of algebraic block codes . US Patent Number 4 , 633 ,470, December 1986 . Welch, L.R., Berlekamp, E.R. Error correction of algebraic block codes. US Patent Number 4,633,470, December 1986.","journal-title":"US Patent Number"},{"key":"e_1_2_2_19_1","first-page":"90","article-title":"Quarterly Progress Report, Research Laboratory of Electronics","volume":"48","author":"Wozencraft J.M.","year":"1958","unstructured":"Wozencraft , J.M. List Decoding . Quarterly Progress Report, Research Laboratory of Electronics , MIT , 48 ( 1958 ), 90 -- 95 . Wozencraft, J.M. List Decoding. Quarterly Progress Report, Research Laboratory of Electronics, MIT, 48 (1958), 90--95.","journal-title":"MIT"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/1467247.1467269","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/1467247.1467269","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:41Z","timestamp":1750253381000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/1467247.1467269"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["10.1145\/1467247.1467269"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1145\/1467247.1467269","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2009,3]]},"assertion":[{"value":"2009-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}