{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:05Z","timestamp":1750695005451,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","funder":[{"name":"NSF (National Science Foundation)","award":["CCF-1813135,CCF-2131899,CCF-2133154,CCF-2231157"],"award-info":[{"award-number":["CCF-1813135,CCF-2131899,CCF-2133154,CCF-2231157"]}]},{"name":"Bill and Melinda Gates Foundation","award":["Anna Karlin's Bill and Melinda Gates Endowed Chair"],"award-info":[{"award-number":["Anna Karlin's Bill and Melinda Gates Endowed Chair"]}]},{"name":"Joan and Irwin Jacobs","award":["MIT Jacobs Presidential Fellowship"],"award-info":[{"award-number":["MIT Jacobs Presidential Fellowship"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718206","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:24:47Z","timestamp":1750026287000},"page":"855-866","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["List-Decoding Capacity Implies Capacity on the \ud835\udc5e-ary Symmetric Channel"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-4082-9836","authenticated-orcid":false,"given":"Francisco","family":"Pernice","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4829-8358","authenticated-orcid":false,"given":"Oscar","family":"Sprumont","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2345-2531","authenticated-orcid":false,"given":"Mary","family":"Wootters","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00020"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1561\/0100000123"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2462817"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649634"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2009.2021379"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2401.15034"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2310.12898"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585128"},{"key":"e_1_3_2_1_10_1","volume-title":"Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bound. arXiv preprint","author":"Chen Yeyuan","year":"2024","unstructured":"Yeyuan Chen and Zihan Zhang. 2024. Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton Bound. arXiv preprint, 2024."},{"key":"e_1_3_2_1_11_1","volume-title":"Wescon Convention Record, Part 2, 94\u2013104","author":"Elias Peter","year":"1957","unstructured":"Peter Elias. 1957. List decoding for noisy channels. Wescon Convention Record, Part 2, 94\u2013104."},{"key":"e_1_3_2_1_12_1","unstructured":"George D. Forney. 1966. Concatenated Codes. MIT Press."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1962.1057683"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3131992"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00019"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806747"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3127126"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.911222"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2059572"},{"key":"e_1_3_2_1_20_1","unstructured":"Venkatesan Guruswami Atri Rudra and Madhu Sudan. 2023. Essential coding theory. https:\/\/cse.buffalo.edu\/faculty\/atri\/courses\/coding-theory\/book\/web-coding-book.pdf"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2246813"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488715"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3506668"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.27"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2010.5513670"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.2015.V011A005"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00029"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897584"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2280915"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITW.2016.7606832"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.3041650"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258573"},{"volume-title":"The theory of error correcting codes","author":"MacWilliams Florence","key":"e_1_3_2_1_33_1","unstructured":"Florence MacWilliams and Neil Sloane. 1977. The theory of error correcting codes. North-Holland Publishing Company."},{"key":"e_1_3_2_1_34_1","first-page":"101","article-title":"Probabilistic Characteristics of Graphs with Large Connectivity","volume":"10","author":"Margulis Grigory A.","year":"1974","unstructured":"Grigory A. Margulis. 1974. Probabilistic Characteristics of Graphs with Large Connectivity. Problems of Information Transmission, 10, 2 (1974), 101\u2013108.","journal-title":"Problems of Information Transmission"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00050"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2023.3286452"},{"key":"e_1_3_2_1_37_1","first-page":"129","article-title":"An approximate zero-one law","volume":"61","author":"Russo Lucio","year":"1982","unstructured":"Lucio Russo. 1982. An approximate zero-one law. Probability Theory and Related Fields, 61, 1 (1982), 129\u2013139.","journal-title":"Probability Theory and Related Fields"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Eren Sasoglu. 2011. Polar Coding Theorems for Discrete Systems. PhD thesis.","DOI":"10.1109\/ISIT.2012.6283740"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Shashank Srivastava. 2024. Improved List Size for Folded Reed-Solomon Codes. arXiv preprint arXiv:2410.09031.","DOI":"10.1137\/1.9781611978322.64"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01895691"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2024.3402171"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300004466"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2003.822604"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488716"},{"key":"e_1_3_2_1_46_1","first-page":"90","article-title":"List decoding","author":"Wozencraft John M.","year":"1958","unstructured":"John M. Wozencraft. 1958. List decoding. Quarterly Progress Report, Research Laboratory of Electronics, 90\u201395.","journal-title":"Quarterly Progress Report, Research Laboratory of Electronics"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57843-9_29"},{"key":"e_1_3_2_1_48_1","first-page":"29","article-title":"List concatenated decoding","volume":"17","author":"Zyablov Victor Vasilievich","year":"1981","unstructured":"Victor Vasilievich Zyablov and Mark Semenovich Pinsker. 1981. List concatenated decoding. Problemy Peredachi Informatsii, 17, 4 (1981), 29\u201333.","journal-title":"Problemy Peredachi Informatsii"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718206","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:43:39Z","timestamp":1750693419000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":48,"alternative-id":["10.1145\/3717823.3718206","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718206","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}