{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:11:28Z","timestamp":1750306288902,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":33,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,6,19]],"date-time":"2016-06-19T00:00:00Z","timestamp":1466294400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,6,19]]},"DOI":"10.1145\/2897518.2897526","type":"proceedings-article","created":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T13:04:07Z","timestamp":1465563847000},"page":"227-235","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Efficiently decoding Reed-Muller codes from random errors"],"prefix":"10.1145","author":[{"given":"Ramprasad","family":"Saptharishi","sequence":"first","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amir","family":"Shpilka","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ben Lee","family":"Volk","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,6,19]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746575"},{"key":"e_1_3_2_1_2_1","volume-title":"The Probabilistic Method","author":"Alon N.","year":"1992","unstructured":"N. Alon and J. H. Spencer . The Probabilistic Method . John Wiley , 1992 . N. Alon and J. H. Spencer. The Probabilistic Method. John Wiley, 1992."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/LCOMM.2008.080017"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89520"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/646506.694190"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746543"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958033.1958049"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2007.895188"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.826632"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.864425"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1167813.1705194"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.335964"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374417"},{"key":"e_1_3_2_1_16_1","volume-title":"Essential Coding Theory","author":"Guruswami V.","year":"2014","unstructured":"V. Guruswami , A. Rudra , and M. Sudan . Essential Coding Theory . 2014 . Available at http:\/\/www.cse.buffalo.edu\/faculty\/atri\/ courses\/coding-theory\/book\/. V. Guruswami, A. Rudra, and M. Sudan. Essential Coding Theory. 2014. Available at http:\/\/www.cse.buffalo.edu\/faculty\/atri\/ courses\/coding-theory\/book\/."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.782097"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1950.tb00463.x"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.844080"},{"key":"e_1_3_2_1_20_1","first-page":"541","article-title":"On the number of Reed-Muller code correctable errors","volume":"191","author":"Krichevskiy R. E.","year":"1970","unstructured":"R. E. Krichevskiy . On the number of Reed-Muller code correctable errors . Dokl. Sov. Acad. Sci. , 191 : 541 \u2013 547 , 1970 . R. E. Krichevskiy. On the number of Reed-Muller code correctable errors. Dokl. Sov. Acad. Sci., 191:541\u2013547, 1970.","journal-title":"Dokl. Sov. Acad. Sci."},{"key":"e_1_3_2_1_21_1","volume-title":"\u00b8 Sa\u00b8so\u02d8 glu, and R. L. Urbanke. Reed-muller codes achieve capacity on the binary erasure channel under MAP decoding. CoRR, abs\/1505.05831","author":"Kudekar S.","year":"2015","unstructured":"S. Kudekar , M. Mondelli , E. \u00b8 Sa\u00b8so\u02d8 glu, and R. L. Urbanke. Reed-muller codes achieve capacity on the binary erasure channel under MAP decoding. CoRR, abs\/1505.05831 , 2015 . S. Kudekar, M. Mondelli, E. \u00b8 Sa\u00b8so\u02d8 glu, and R. L. Urbanke. Reed-muller codes achieve capacity on the binary erasure channel under MAP decoding. CoRR, abs\/1505.05831, 2015."},{"key":"e_1_3_2_1_22_1","volume-title":"Reed-muller codes achieve capacity on erasure channels. CoRR, abs\/1505.05123","author":"Kumar S.","year":"2015","unstructured":"S. Kumar and H. D. Pfister . Reed-muller codes achieve capacity on erasure channels. CoRR, abs\/1505.05123 , 2015 . S. Kumar and H. D. Pfister. Reed-muller codes achieve capacity on erasure channels. CoRR, abs\/1505.05123, 2015."},{"key":"e_1_3_2_1_23_1","volume-title":"The theory of error correcting codes. Number v. 2 in North-Holland mathematical library","author":"MacWilliams F. J.","year":"1977","unstructured":"F. J. MacWilliams and N. J. A. Sloane . The theory of error correcting codes. Number v. 2 in North-Holland mathematical library . North-Holland Publishing Company , 1977 . F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Number v. 2 in North-Holland mathematical library. North-Holland Publishing Company, 1977."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2014.2345069"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/IREPGELC.1954.6499441"},{"key":"e_1_3_2_1_26_1","volume-title":"A class of multiple-error-correcting codes and the decoding scheme. Trans. of the IRE Professional Group on Information Theory (TIT), 4:38\u201349","author":"Reed I. S.","year":"1954","unstructured":"I. S. Reed . A class of multiple-error-correcting codes and the decoding scheme. Trans. of the IRE Professional Group on Information Theory (TIT), 4:38\u201349 , 1954 . I. S. Reed. A class of multiple-error-correcting codes and the decoding scheme. Trans. of the IRE Professional Group on Information Theory (TIT), 4:38\u201349, 1954."},{"key":"e_1_3_2_1_27_1","volume-title":"Efficiently decoding reed-muller codes from random errors. CoRR, abs\/1503.09092","author":"Saptharishi R.","year":"2015","unstructured":"R. Saptharishi , A. Shpilka , and B. L. Volk . Efficiently decoding reed-muller codes from random errors. CoRR, abs\/1503.09092 , 2015 . R. Saptharishi, A. Shpilka, and B. L. Volk. Efficiently decoding reed-muller codes from random errors. CoRR, abs\/1503.09092, 2015."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"issue":"3","key":"e_1_3_2_1_31_1","first-page":"80","article-title":"Decoding of Reed-Muller Codes with a Large Number of Errors","volume":"28","author":"Sidel\u2019nikov V. M.","year":"1992","unstructured":"V. M. Sidel\u2019nikov and A. S. Pershakov . Decoding of Reed-Muller Codes with a Large Number of Errors . Problems Inform. Transmission , 28 ( 3 ): 80 \u2013 94 , 1992 . V. M. Sidel\u2019nikov and A. S. Pershakov. Decoding of Reed-Muller Codes with a Large Number of Errors. Problems Inform. Transmission, 28(3):80\u201394, 1992.","journal-title":"Problems Inform. Transmission"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0439"},{"key":"e_1_3_2_1_33_1","volume-title":"Error correction for algebraic block codes","author":"Welch L. R.","year":"1986","unstructured":"L. R. Welch and E. R. Berlekamp . Error correction for algebraic block codes , 1986 . US Patent 4,633,470. Introduction Reed-Muller Codes Background Decoding Erasures to Decoding Errors Our Contributions Related Literature Notation and Terminology Proof Techniques Decoding Algorithm For Reed-Muller Codes Acknowledgments References L. R. Welch and E. R. Berlekamp. Error correction for algebraic block codes, 1986. US Patent 4,633,470. Introduction Reed-Muller Codes Background Decoding Erasures to Decoding Errors Our Contributions Related Literature Notation and Terminology Proof Techniques Decoding Algorithm For Reed-Muller Codes Acknowledgments References"}],"event":{"name":"STOC '16: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Cambridge MA USA","acronym":"STOC '16"},"container-title":["Proceedings of the forty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897526","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897518.2897526","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:02Z","timestamp":1750221542000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897526"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,19]]},"references-count":33,"alternative-id":["10.1145\/2897518.2897526","10.1145\/2897518"],"URL":"https:\/\/doi.org\/10.1145\/2897518.2897526","relation":{},"subject":[],"published":{"date-parts":[[2016,6,19]]},"assertion":[{"value":"2016-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}