{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T14:52:02Z","timestamp":1784299922481,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1816372"],"award-info":[{"award-number":["CCF-1816372"]}],"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":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451126","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1527-1536","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Near-linear time decoding of Ta-Shma\u2019s codes via splittable regularity"],"prefix":"10.1145","author":[{"given":"Fernando Granha","family":"Jeronimo","sequence":"first","affiliation":[{"name":"University of Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shashank","family":"Srivastava","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Madhur","family":"Tulsiani","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"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\/FOCS.2019.00021"},{"key":"e_1_3_2_1_3_1","first-page":"1992","article-title":"Construction of asymptotically good, low-rate error-correcting codes through pseudo-random graphs","volume":"28","author":"Alon N.","year":"1992","unstructured":"N. Alon, J. Bruck, J. Naor, M. Naor, and R. Roth. 1992. Construction of asymptotically good, low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory, 28, 1992. Pages 509\u2013516.","journal-title":"IEEE Transactions on Information Theory"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007371"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the International Congress of Mathematicians. Pages 637\u2013648","author":"Arora Sanjeev","year":"2002","unstructured":"Sanjeev Arora. 2002. How NP got a new definition: a survey of probabilistically checkable proofs. In Proceedings of the International Congress of Mathematicians. Pages 637\u2013648."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250823"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.95"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2822686"},{"key":"e_1_3_2_1_9_1","volume-title":"Probability and Measure","author":"Billingsley Patrick","unstructured":"Patrick Billingsley. 1995. Probability and Measure. J. Wiley and Sons."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Greg Bodwin and Santosh Vempala. 2020. A Unified View of Graph Regularity via Matrix Decompositions.","DOI":"10.1002\/rsa.21053"},{"key":"e_1_3_2_1_11_1","unstructured":"Andrej Bogdanov. 2012. A different way to improve the bias via expanders. Lecture notes. http:\/\/www.cse.cuhk.edu.hk\/~andrejb\/csc5060\/notes\/12L12.pdf"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000050"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2873054"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.24"},{"key":"e_1_3_2_1_15_1","first-page":"336","volume-title":"Direct Sum Testing. ITCS '15","author":"David Roee","year":"2015","unstructured":"Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar. 2015. Direct Sum Testing. ITCS '15. ACM. Pages 327\u2013336. isbn:978-1-4503-3333-7"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00088"},{"key":"e_1_3_2_1_17_1","volume-title":"Locally testable codes via high-dimensional expanders. arXiv preprint arXiv:2005.01045","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, 2020."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.129"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.94"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.27"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897543"},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the 37th IEEE Symposium on Foundations of Computer Science.","author":"Frieze A.","unstructured":"A. Frieze and R. Kannan. 1996. The regularity lemma and approximation schemes for dense problems. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1952.tb01393.x"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1027914.1027924"},{"key":"e_1_3_2_1_25_1","volume-title":"Coding and Cryptology","author":"Guruswami Venkatesan","unstructured":"Venkatesan Guruswami. 2009. List Decoding of Binary Codes\u2013A Brief Survey of Some Recent Results. In Coding and Cryptology. Springer Berlin Heidelberg. Pages 97\u2013106."},{"key":"e_1_3_2_1_26_1","unstructured":"Venkatesan Guruswami. 2010. Bridging Shannon and Hamming: List Error-Correction with Optimal Rate. In ICM."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875548"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.855587"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132518"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Venkatesan Guruswami and Ali Kemal Sinop. 2011. Lasserre Hierarchy Higher Eigenvalues and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives. In FOCS. Pages 482\u2013491.","DOI":"10.1109\/FOCS.2011.36"},{"key":"e_1_3_2_1_31_1","first-page":"2006","article-title":"Expander Graphs and Their","volume":"43","author":"Hoory Shlomo","year":"2006","unstructured":"Shlomo Hoory, Nathan Linial, and Avi Wigderson. 2006. Expander Graphs and Their Applications. Bull. Amer. Math. Soc., 43, 4, Aug., 2006. Pages 439\u2013562.","journal-title":"Applications. Bull. Amer. Math. Soc."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536435"},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings of the 29th ACM Symposium on Theory of Computing. Pages 220\u2013229","author":"Impagliazzo Russell","year":"1997","unstructured":"Russell Impagliazzo and Avi Wigderson. 1997. P=BPP unless E has sub-exponential circuits. In Proceedings of the 29th ACM Symposium on Theory of Computing. Pages 220\u2013229."},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the 61st IEEE Symposium on Foundations of Computer Science.","author":"Jeronimo Fernando Granha","year":"2020","unstructured":"Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, and Madhur Tulsiani. 2020. Unique Decoding of Explicit \\epsilon -balanced Codes Near the Gilbert\u2013Varshamov Bound. In Proceedings of the 61st IEEE Symposium on Foundations of Computer Science."},{"key":"e_1_3_2_1_35_1","volume-title":"Spectral algorithms","author":"Kannan Ravindran","unstructured":"Ravindran Kannan and Santosh Vempala. 2009. Spectral algorithms. Now Publishers Inc."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Y. Kohayakawa and V. R\u00f6dl. 2002. Szemer\u00e9di's regularity lemma and quasi-randomness. In Recent advances in algorithms and combinatorics. Springer Berlin. citeseer.ist.psu.edu\/kohayakawa02szemeredis.html","DOI":"10.1007\/0-387-22444-0_9"},{"key":"e_1_3_2_1_37_1","volume-title":"Conference on Learning Theory, COLT 2020","author":"Lee Yin Tat","year":"2020","unstructured":"Yin Tat Lee and Swati Padmanabhan. 2020. An \\mathaccent \"0365O(m\/\\varepsilon ^3.5)-Cost Algorithm for Semidefinite Programs with Diagonal Constraints. In Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria]. 125, Pages 3069\u20133119."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055688"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0047-x"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a009"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.38"},{"key":"e_1_3_2_1_42_1","volume-title":"Linear-time Erasure List-decoding of Expander Codes. In 2020 IEEE International Symposium on Information Theory (ISIT). Pages 379\u2013383","author":"Ron-Zewi N.","unstructured":"N. Ron-Zewi, M. Wootters, and G. Z\u00e9mor. 2020. Linear-time Erasure List-decoding of Expander Codes. In 2020 IEEE International Symposium on Information Theory (ISIT). Pages 379\u2013383."},{"key":"e_1_3_2_1_43_1","volume-title":"Functional Analysis","author":"Rudin W.","unstructured":"W. Rudin. 1991. Functional Analysis. McGraw-Hill. isbn:9780070542365"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556667"},{"key":"e_1_3_2_1_45_1","first-page":"4528","volume-title":"Epsilon-balanced Codes. In Proceedings of the 49th ACM Symposium on Theory of Computing. STOC 2017. ACM. Pages 238\u2013251","author":"Ta-Shma Amnon","year":"2017","unstructured":"Amnon Ta-Shma. 2017. Explicit, Almost Optimal, Epsilon-balanced Codes. In Proceedings of the 49th ACM Symposium on Theory of Computing. STOC 2017. ACM. Pages 238\u2013251. isbn:978-1-4503-4528-6"},{"key":"e_1_3_2_1_46_1","volume-title":"Proceedings of the 24th IEEE Conference on Computational Complexity.","author":"Trevisan L.","unstructured":"L. Trevisan, M. Tulsiani, and S. Vadhan. 2009. Boosting, Regularity and Efficiently Simulating every High-Entropy Distribution. In Proceedings of the 24th IEEE Conference on Computational Complexity."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Salil P. Vadhan. 2012. Pseudorandomness. Now Publishers Inc.. isbn:1601985940","DOI":"10.1561\/9781601985958"},{"key":"e_1_3_2_1_48_1","first-page":"1957","article-title":"Estimate of the Number of Signals in Error Correcting Codes","volume":"117","author":"Varshamov R.R.","year":"1957","unstructured":"R.R. Varshamov. 1957. Estimate of the Number of Signals in Error Correcting Codes. Doklady Akademii Nauk SSSR, 117, 1957. Pages 739\u2013741.","journal-title":"Doklady Akademii Nauk SSSR"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451126","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451126","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451126","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451126"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":48,"alternative-id":["10.1145\/3406325.3451126","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451126","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}