{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T05:22:41Z","timestamp":1774070561609,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":53,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["GRFP, DMS-1638352, CCF-1412958, CCF-1900460"],"award-info":[{"award-number":["GRFP, DMS-1638352, CCF-1412958, CCF-1900460"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006112","name":"Microsoft Research","doi-asserted-by":"publisher","award":["PhD Fellowship"],"award-info":[{"award-number":["PhD Fellowship"]}],"id":[{"id":"10.13039\/100006112","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585128","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1488-1501","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Generic Reed-Solomon Codes Achieve List-Decoding Capacity"],"prefix":"10.1145","author":[{"given":"Joshua","family":"Brakensiek","sequence":"first","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Sivakanth","family":"Gopi","sequence":"additional","affiliation":[{"name":"Microsoft Research, USA"}]},{"given":"Visu","family":"Makam","sequence":"additional","affiliation":[{"name":"Radix Trading Europe, Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2034780"},{"key":"e_1_3_2_1_2_1","volume-title":"Generic Reed-Solomon codes achieve list-decoding capacity. CoRR, abs\/2206.05256","author":"Brakensiek Joshua","year":"2022","unstructured":"Joshua Brakensiek , Sivakanth Gopi , and Visu Makam . 2022. Generic Reed-Solomon codes achieve list-decoding capacity. CoRR, abs\/2206.05256 ( 2022 ), https:\/\/doi.org\/10.48550\/arXiv.2206.05256 arXiv:2206.05256. 10.48550\/arXiv.2206.05256 Joshua Brakensiek, Sivakanth Gopi, and Visu Makam. 2022. Generic Reed-Solomon codes achieve list-decoding capacity. CoRR, abs\/2206.05256 (2022), https:\/\/doi.org\/10.48550\/arXiv.2206.05256 arXiv:2206.05256."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2022.3187366"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00055"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447335"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2013.6620554"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2014.6875141"},{"key":"e_1_3_2_1_8_1","volume-title":"Asymptotic methods in analysis. 4","author":"De Bruijn Nicolaas Govert","unstructured":"Nicolaas Govert De Bruijn . 1981. Asymptotic methods in analysis. 4 , Courier Corporation . Nicolaas Govert De Bruijn. 1981. Asymptotic methods in analysis. 4, Courier Corporation."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2017.01.018"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1080\/03081087.2017.1337058"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214010"},{"key":"e_1_3_2_1_12_1","volume-title":"List Decoding for Noisy Channels. In IRE WESCON Convention Record","author":"Elias P","year":"1957","unstructured":"P Elias . 1957 . List Decoding for Noisy Channels. In IRE WESCON Convention Record , 1957. 2, 94\u2013104. P Elias. 1957. List Decoding for Noisy Channels. In IRE WESCON Convention Record, 1957. 2, 94\u2013104."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2022.3148779"},{"key":"e_1_3_2_1_14_1","unstructured":"Ernst M Gabidulin. [n. d.]. Rank-metric codes and applications. Moscow Inst. Phys. Technol. State Univ. Dolgoprudny Russia.[Online]. http:\/\/iitp.ru\/upload\/content\/839\/Gabidulin.pdf \t\t\t\t  Ernst M Gabidulin. [n. d.]. Rank-metric codes and applications. Moscow Inst. Phys. Technol. State Univ. Dolgoprudny Russia.[Online]. http:\/\/iitp.ru\/upload\/content\/839\/Gabidulin.pdf"},{"key":"e_1_3_2_1_15_1","volume-title":"Rank codes","author":"Gabidulin Ernst M","unstructured":"Ernst M Gabidulin . 2021. Rank codes . TUM. University Press . Ernst M Gabidulin. 2021. Rank codes. TUM. University Press."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.95"},{"key":"e_1_3_2_1_17_1","volume-title":"List-decoding and list-recovery of Reed-Solomon codes beyond the Johnson radius for any rate. CoRR, abs\/2105.14754","author":"Goldberg Eitan","year":"2021","unstructured":"Eitan Goldberg , Chong Shangguan , and Itzhak Tamo . 2021. List-decoding and list-recovery of Reed-Solomon codes beyond the Johnson radius for any rate. CoRR, abs\/2105.14754 ( 2021 ), arXiv:2105.14754. arxiv:2105.14754 Eitan Goldberg, Chong Shangguan, and Itzhak Tamo. 2021. List-decoding and list-recovery of Reed-Solomon codes beyond the Johnson radius for any rate. CoRR, abs\/2105.14754 (2021), arXiv:2105.14754. arxiv:2105.14754"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT50566.2022.9834849"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.136"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00074"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00011"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.911222"},{"key":"e_1_3_2_1_23_1","unstructured":"Venkatesan Guruswami Atri Rudra and Madhu Sudan. 2012. Essential coding theory. Draft available at http:\/\/www. cse. buffalo. edu\/ atri\/courses\/coding-theory\/book. \t\t\t\t  Venkatesan Guruswami Atri Rudra and Madhu Sudan. 2012. Essential coding theory. Draft available at http:\/\/www. cse. buffalo. edu\/ atri\/courses\/coding-theory\/book."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743426"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214009"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488715"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2014.6874913"},{"key":"e_1_3_2_1_28_1","volume-title":"d.]. Notes on Coding Theory (Chapter 5\u2014Generalized Reed-Solomon Codes). Department of Mathematics","author":"Hall JI","unstructured":"JI Hall . [n. d.]. Notes on Coding Theory (Chapter 5\u2014Generalized Reed-Solomon Codes). Department of Mathematics , Michigan State University available online at http:\/\/users. math. msu. edu\/users\/jhall\/classes\/codenotes\/coding-notes. html (Jan. 7, 2015 revision). JI Hall. [n. d.]. Notes on Coding Theory (Chapter 5\u2014Generalized Reed-Solomon Codes). Department of Mathematics, Michigan State University available online at http:\/\/users. math. msu. edu\/users\/jhall\/classes\/codenotes\/coding-notes. html (Jan. 7, 2015 revision)."},{"key":"e_1_3_2_1_29_1","volume-title":"Erasure Coding in Windows Azure Storage. In 2012 USENIX Annual Technical Conference","author":"Huang Cheng","year":"2012","unstructured":"Cheng Huang , Huseyin Simitci , Yikang Xu , Aaron Ogus , Brad Calder , Parikshit Gopalan , Jin Li , and Sergey Yekhanin . 2012 . Erasure Coding in Windows Azure Storage. In 2012 USENIX Annual Technical Conference , Boston, MA, USA , June 13-15, 2012, Gernot Heiser and Wilson C. Hsieh (Eds.). USENIX Association, 15\u201326. https:\/\/www.usenix.org\/conference\/atc12\/technical-sessions\/presentation\/huang Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, and Sergey Yekhanin. 2012. Erasure Coding in Windows Azure Storage. In 2012 USENIX Annual Technical Conference, Boston, MA, USA, June 13-15, 2012, Gernot Heiser and Wilson C. Hsieh (Eds.). USENIX Association, 15\u201326. https:\/\/www.usenix.org\/conference\/atc12\/technical-sessions\/presentation\/huang"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0143-x"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-018-0165-7"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1962.1057714"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00029"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1323345"},{"key":"e_1_3_2_1_35_1","volume-title":"The theory of error correcting codes. 16","author":"MacWilliams Florence Jessie","unstructured":"Florence Jessie MacWilliams and Neil James Alexander Sloane . 1977. The theory of error correcting codes. 16 , Elsevier . Florence Jessie MacWilliams and Neil James Alexander Sloane. 1977. The theory of error correcting codes. 16, Elsevier."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00050"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1090\/jams\/864"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.29"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0108018"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2022.3194521"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591797"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384295"},{"key":"e_1_3_2_1_44_1","volume-title":"Warm BLOB Storage System. In 11th USENIX Symposium on Operating Systems Design and Implementation, OSDI \u201914","author":"Subramanian Muralidhar","year":"2014","unstructured":"Muralidhar Subramanian , Wyatt Lloyd , Sabyasachi Roy , Cory Hill , Ernest Lin , Weiwen Liu , Satadru Pan , Shiva Shankar , Sivakumar Viswanathan , Linpeng Tang , and Sanjeev Kumar . 2014 . f4: Facebook\u2019s Warm BLOB Storage System. In 11th USENIX Symposium on Operating Systems Design and Implementation, OSDI \u201914 , Broomfield, CO, USA , October 6-8, 2014, Jason Flinn and Hank Levy (Eds.). USENIX Association, 383\u2013398. https:\/\/www.usenix.org\/conference\/osdi14\/technical-sessions\/presentation\/muralidhar Muralidhar Subramanian, Wyatt Lloyd, Sabyasachi Roy, Cory Hill, Ernest Lin, Weiwen Liu, Satadru Pan, Shiva Shankar, Sivakumar Viswanathan, Linpeng Tang, and Sanjeev Kumar. 2014. f4: Facebook\u2019s Warm BLOB Storage System. In 11th USENIX Symposium on Operating Systems Design and Implementation, OSDI \u201914, Broomfield, CO, USA, October 6-8, 2014, Jason Flinn and Hank Levy (Eds.). USENIX Association, 383\u2013398. https:\/\/www.usenix.org\/conference\/osdi14\/technical-sessions\/presentation\/muralidhar"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0439"},{"key":"e_1_3_2_1_46_1","volume-title":"Reed-Solomon codes and their applications","author":"Wicker Stephen B","unstructured":"Stephen B Wicker and Vijay K Bhargava . 1999. Reed-Solomon codes and their applications . John Wiley & Sons . Stephen B Wicker and Vijay K Bhargava. 1999. Reed-Solomon codes and their applications. John Wiley & Sons."},{"key":"e_1_3_2_1_47_1","first-page":"90","article-title":"List decoding","volume":"48","author":"Wozencraft John M","year":"1958","unstructured":"John M Wozencraft . 1958 . List decoding . Quarterly Progress Report , 48 (1958), 90 \u2013 95 . John M Wozencraft. 1958. List decoding. Quarterly Progress Report, 48 (1958), 90\u201395.","journal-title":"Quarterly Progress Report"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/NetCod.2013.6570836"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2932663"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2955106"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT44484.2020.9174524"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-09519-5_73"},{"issue":"4","key":"e_1_3_2_1_53_1","first-page":"29","article-title":"List cascade decoding","volume":"17","author":"Zyablov Victor Vasilievich","year":"1981","unstructured":"Victor Vasilievich Zyablov and Mark Semenovich Pinsker . 1981 . List cascade decoding . Problemy Peredachi Informatsii , 17 ( 4 ): 29 \u2013 33 . Victor Vasilievich Zyablov and Mark Semenovich Pinsker. 1981. List cascade decoding. Problemy Peredachi Informatsii, 17(4):29\u201333.","journal-title":"Problemy Peredachi Informatsii"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585128","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585128","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585128","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585128"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":53,"alternative-id":["10.1145\/3564246.3585128","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585128","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}