{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:15Z","timestamp":1781031435982,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":91,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2424441"],"award-info":[{"award-number":["DMS-2424441"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2212136"],"award-info":[{"award-number":["CCF-2212136"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800886","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1789-1799","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["High Rate Efficient Local List Decoding from HDX"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6248-6574","authenticated-orcid":false,"given":"Yotam","family":"Dikstein","sequence":"first","affiliation":[{"name":"Institute for Advanced Study at Princeton, Princeton, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7695-6063","authenticated-orcid":false,"given":"Max","family":"Hopkins","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8668-2174","authenticated-orcid":false,"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[{"name":"Columbia University, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3236-9796","authenticated-orcid":false,"given":"Russell","family":"Impagliazzo","sequence":"additional","affiliation":[{"name":"University of California at San Diego, San Diego, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.85"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.119713"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492581"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316385"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585114"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258642"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2402.00850"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649714"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718170"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718197"},{"key":"e_1_3_2_1_12_1","volume-title":"Servedio","author":"Blanc Guy","year":"2026","unstructured":"Guy Blanc, Yuhao Huang, Tal Malkin, and Rocco A. Servedio. 2026. Is Nasty Noise Actually Harder than Malicious Noise? To appear"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.72"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.61"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3097347"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49116-3_8"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2982445.2982455"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451059"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2025.104131"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00088"},{"key":"e_1_3_2_1_22_1","volume-title":"Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers. arXiv preprint arXiv:2308.09582, 0","author":"Dikstein Yotam","year":"2023","unstructured":"Yotam Dikstein and Irit Dinur. 2023. Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers. arXiv preprint arXiv:2308.09582, 0 (2023), 56 pages."},{"key":"e_1_3_2_1_23_1","volume-title":"Locally testable codes via high-dimensional expanders. arXiv preprint arXiv:2005.01045, 0","author":"Dikstein Yotam","year":"2020","unstructured":"Yotam Dikstein, Irit Dinur, Prahladh Harsha, and Noga Ron-Zewi. 2020. Locally testable codes via high-dimensional expanders. arXiv preprint arXiv:2005.01045, 0 (2020), 75 pages."},{"key":"e_1_3_2_1_24_1","volume-title":"Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs. arXiv preprint arXiv:2402.01078, 0","author":"Dikstein Yotam","year":"2024","unstructured":"Yotam Dikstein, Irit Dinur, and Alexander Lubotzky. 2024. Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs. arXiv preprint arXiv:2402.01078, 0 (2024), 90 pages."},{"key":"e_1_3_2_1_25_1","volume-title":"Chernoff Bounds and Reverse Hypercontractivity on HDX. arXiv preprint arXiv:2404.10961, 0","author":"Dikstein Yotam","year":"2024","unstructured":"Yotam Dikstein and Max Hopkins. 2024. Chernoff Bounds and Reverse Hypercontractivity on HDX. arXiv preprint arXiv:2404.10961, 0 (2024), 124 pages."},{"key":"e_1_3_2_1_26_1","unstructured":"Yotam Dikstein Max Hopkins Russell Impagliazzo and Toniann Pitassi. 2026. High Rate Efficient Local List Decoding from HDX. arxiv:arXiv:2601.22535."},{"key":"e_1_3_2_1_27_1","volume-title":"Locally Testable Codes with constant rate, distance, and locality. arXiv preprint arXiv:2111.04808, 0","author":"Dinur Irit","year":"2021","unstructured":"Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes. 2021. Locally Testable Codes with constant rate, distance, and locality. arXiv preprint arXiv:2111.04808, 0 (2021), 37 pages."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.129"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1276650"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.94"},{"key":"e_1_3_2_1_31_1","volume-title":"New codes on high dimensional expanders. arXiv preprint arXiv:2308.15563, 0","author":"Dinur Irit","year":"2023","unstructured":"Irit Dinur, Siqi Liu, and Rachel Yun Zhang. 2023. New codes on high dimensional expanders. arXiv preprint arXiv:2308.15563, 0 (2023), 41 pages."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555307"},{"key":"e_1_3_2_1_33_1","unstructured":"Peter Elias. 1957. List decoding for noisy channels."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00029"},{"key":"e_1_3_2_1_35_1","volume-title":"On Good 2 -Query Locally Testable Codes from Sheaves on High Dimensional Expanders. arXiv preprint arXiv:2208.01778, 0","author":"First Uriya A","year":"2022","unstructured":"Uriya A First and Tali Kaufman. 2022. On Good 2 -Query Locally Testable Codes from Sheaves on High Dimensional Expanders. arXiv preprint arXiv:2208.01778, 0 (2022), 136 pages."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1962.1057683"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2809788"},{"key":"e_1_3_2_1_39_1","volume-title":"List agreement expansion from coboundary expansion. arXiv preprint arXiv:2210.15714, 0","author":"Gotlib Roy","year":"2022","unstructured":"Roy Gotlib and Tali Kaufman. 2022. List agreement expansion from coboundary expansion. arXiv preprint arXiv:2210.15714, 0 (2022), 66 pages."},{"key":"e_1_3_2_1_40_1","volume-title":"Quantum Tanner Color Codes on Qubits with Transversal Gates. arXiv preprint arXiv:2510.07864, 0","author":"Gulshen Kyle","year":"2025","unstructured":"Kyle Gulshen and Tali Kaufman. 2025. Quantum Tanner Color Codes on Qubits with Transversal Gates. arXiv preprint arXiv:2510.07864, 0 (2025), 59 pages."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2503767"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2538766"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422494"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959942"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780562"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_52"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538904"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.013"},{"key":"e_1_3_2_1_51_1","article-title":"Local list recovery of high-rate tensor codes and applications","volume":"49","author":"Hemenway Brett","year":"2019","unstructured":"Brett Hemenway, Noga Ron-Zewi, and Mary Wootters. 2019. Local list recovery of high-rate tensor codes and applications. SIAM J. Comput., 49, 4 (2019), FOCS17\u2013157.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585189"},{"key":"e_1_3_2_1_53_1","volume-title":"Explicit Lossless Vertex Expanders. arXiv preprint arXiv:2504.15087, 0","author":"Hsieh Jun-Ting","year":"2025","unstructured":"Jun-Ting Hsieh, Alexander Lubotzky, Sidhanth Mohanty, Assaf Reiner, and Rachel Yun Zhang. 2025. Explicit Lossless Vertex Expanders. arXiv preprint arXiv:2504.15087, 0 (2025), 43 pages."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492584"},{"key":"e_1_3_2_1_55_1","volume-title":"Hardness as randomness: A survey of universal derandomization. arXiv preprint cs\/0304040, 0","author":"Impagliazzo Russell","year":"2003","unstructured":"Russell Impagliazzo. 2003. Hardness as randomness: A survey of universal derandomization. arXiv preprint cs\/0304040, 0 (2003), 23 pages."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683994"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374460"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718302"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451126"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804678"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"e_1_3_2_1_63_1","volume-title":"Edge transitive Ramanujan graphs and highly symmetric LDPC good codes. arXiv preprint arXiv:1108.2960, 0","author":"Kaufman Tali","year":"2011","unstructured":"Tali Kaufman and Alexander Lubotzky. 2011. Edge transitive Ramanujan graphs and highly symmetric LDPC good codes. arXiv preprint arXiv:1108.2960, 0 (2011), 30 pages."},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554842"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188782"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-019-3847-0"},{"key":"e_1_3_2_1_67_1","volume-title":"53rd Annual ACM SIGACT Symposium on Theory of Computing","author":"Kaufman Tali","year":"2021","unstructured":"Tali Kaufman and Ran J. Tessler. 2021. New cosystolic expanders from tensors imply explicit Quantum LDPC codes with \u03a9 (\u221a n log^ k n) distance. In STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021. ACM, USA. 1317\u20131329."},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051093"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00029"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806748"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629416"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00117"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22185"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510015"},{"key":"e_1_3_2_1_76_1","volume-title":"Asymptotically good quantum and locally testable classical LDPC codes. arXiv preprint arXiv:2111.03654, 0","author":"Panteleev Pavel","year":"2021","unstructured":"Pavel Panteleev and Gleb Kalachev. 2021. Asymptotically good quantum and locally testable classical LDPC codes. arXiv preprint arXiv:2111.03654, 0 (2021), 31 pages."},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/1059513.1059516"},{"key":"e_1_3_2_1_80_1","volume-title":"Expander codes","author":"Sipser Michael","year":"2002","unstructured":"Michael Sipser and Daniel A Spielman. 2002. Expander codes. IEEE transactions on Information Theory, 42, 6 (2002), 1710\u20131722."},{"key":"e_1_3_2_1_81_1","volume-title":"List Decoding Expander-Based Codes up to Capacity in Near-Linear Time. arXiv preprint arXiv:2504.20333, 0","author":"Srivastava Shashank","year":"2025","unstructured":"Shashank Srivastava and Madhur Tulsiani. 2025. List Decoding Expander-Based Codes up to Capacity in Near-Linear Time. arXiv preprint arXiv:2504.20333, 0 (2025), 19 pages."},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0439"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301397"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238187"},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502099"},{"key":"e_1_3_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0233-x"},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509997"},{"key":"e_1_3_2_1_88_1","volume-title":"Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of batch evaluation. arXiv preprint arXiv:1601.04743, 0","author":"Williams Ryan","year":"2016","unstructured":"Ryan Williams. 2016. Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of batch evaluation. arXiv preprint arXiv:1601.04743, 0 (2016), 103 pages."},{"key":"e_1_3_2_1_89_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\u201395.","journal-title":"Quarterly Progress Report"},{"key":"e_1_3_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382790"},{"key":"e_1_3_2_1_91_1","first-page":"15","article-title":"Decoding complexity of low-density codes for transmission in a channel with erasures","volume":"10","author":"Zyablov Victor Vasilievich","year":"1974","unstructured":"Victor Vasilievich Zyablov and Mark Semenovich Pinsker. 1974. Decoding complexity of low-density codes for transmission in a channel with erasures. Problemy Peredachi Informatsii, 10, 1 (1974), 15\u201328.","journal-title":"Problemy Peredachi Informatsii"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800886","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800886","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:01:06Z","timestamp":1781028066000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800886"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":91,"alternative-id":["10.1145\/3798129.3800886","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800886","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}