{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:43:50Z","timestamp":1787341430525,"version":"build-2736575974"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"name":"ERC-CoG","award":["772839"],"award-info":[{"award-number":["772839"]}]},{"name":"Swarnajayanti Fellowship"},{"DOI":"10.13039\/501100001502","name":"Department of Atomic Energy, Government of India","doi-asserted-by":"publisher","award":["12-R&D-TFR-5.01-0500"],"award-info":[{"award-number":["12-R&D-TFR-5.01-0500"]}],"id":[{"id":"10.13039\/501100001502","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["952\/18"],"award-info":[{"award-number":["952\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001501","name":"University Grants Commission","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001501","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We strengthen the notion of double samplers, first introduced by Dinur and Kaufman [``High dimensional expanders imply agreement expanders,\u201d in Proc. 58th IEEE Symp. on Foundations of Comp. Science, IEEE, 2017, pp. 974--985], which are samplers with additional combinatorial properties, and whose existence we prove using high-dimensional expanders. The ABNNR code construction [N. Alon et al., IEEE Trans. Inform. Theory, 38 (1992), pp. 509--516] achieves large distance by starting with a base code $C$ with moderate distance, and then amplifying the distance using a sampler. We show that if the sampler is part of a larger double sampler, then the construction has an efficient list-decoding algorithm. Our algorithm works even if the ABNNR construction is not applied to a base code $C$ but rather to any string. In this case the resulting code is approximate-list-decodable, i.e., the output list contains an approximation to the original input. Our list-decoding algorithm works as follows: It uses a local voting scheme from which it constructs a unique games constraint graph. The constraint graph is an expander, so we can solve unique games efficiently. These solutions are the output of the list-decoder. This is a novel use of a unique games algorithm as a subroutine in a decoding procedure, as opposed to the more common situation in which unique games are used for demonstrating hardness results. Double samplers and high-dimensional expanders are akin to pseudorandom objects in their utility, but they greatly exceed random objects in their combinatorial properties. We believe that these objects hold significant potential for coding theoretic constructions and view this work as demonstrating the power of double samplers in this context.<\/jats:p>","DOI":"10.1137\/19m1276650","type":"journal-article","created":{"date-parts":[[2021,3,9]],"date-time":"2021-03-09T11:23:52Z","timestamp":1615289032000},"page":"301-349","source":"Crossref","is-referenced-by-count":7,"title":["List-Decoding with Double Samplers"],"prefix":"10.1137","volume":"50","author":[{"given":"Irit","family":"Dinur","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prahladh","family":"Harsha","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tali","family":"Kaufman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Inbal Livni","family":"Navon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amnon","family":"Ta-Shma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,3,9]]},"reference":[{"key":"atypb1","first-page":"1412","author":"Alev V. L.","year":"2020","journal-title":"SIAM"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1109\/18.119713"},{"key":"atypb3","first-page":"21","author":"Arora S.","year":"2008","journal-title":"ACM"},{"key":"atypb4","first-page":"687","author":"Chlamtac E.","year":"2006","journal-title":"IEEE"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-005-0237-z"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129115"},{"key":"atypb7","unstructured":"I. Dinur and Y. Gelberg,\n                      A Robustness Result for Expanders\n                      , unpublished manuscript, 2018."},{"key":"atypb8","first-page":"2134","author":"Dinur I.","year":"2019","journal-title":"SIAM"},{"key":"atypb9","first-page":"974","author":"Dinur I.","year":"2017","journal-title":"IEEE"},{"key":"atypb10","unstructured":"E. Friedgut and Y. Iluz,\n                      Hyper-regular Graphs and High Dimensional Expanders\n                      , preprint,https:\/\/arxiv.org\/abs\/2010.03829, 2020."},{"key":"atypb11","first-page":"658","author":"Guruswami V.","year":"2001","journal-title":"IEEE"},{"key":"atypb12","first-page":"126","author":"Guruswami V.","year":"2003","journal-title":"ACM"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.855587"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.911222"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/18.782097"},{"key":"atypb17","first-page":"1858","author":"Guruswami V.","year":"2014","journal-title":"SIAM"},{"key":"atypb18","unstructured":"R. Impagliazzo,\n                      Hardness as randomness: A survey of universal derandomization\n                      , in Proc. Internat. Congress of Mathematicians (Beijing), Vol. 3, Higher Education Press, 2003, pp. 659-672,https:\/\/www.mathunion.org\/fileadmin\/ICM\/Proceedings\/ICM2002.3\/ICM2002.3.ocr.pdf."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/080734030"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/09077299X"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"F. G. Jeronimo, S. Srivastava, and M. Tulsiani,\n                      Near-linear time decoding of Ta-Shma's codes via splittable regularity\n                      , in Proc. 53rd Annual ACM Symp. on Theory of Computing (STOC), ACM, 2021, to appear.","DOI":"10.1145\/3406325.3451126"},{"key":"atypb22","first-page":"773","author":"Kaufman T.","year":"2018","journal-title":"ACM"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-019-3847-0"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a005"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/3051093"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2004.06.007"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"K. Makarychev and Y. Makarychev,\n                      How to play unique games on expanders\n                      , in Proc. 8th International Workshop Approx. & Online Algorithms (WAOA), 2010, pp. 190-200,https:\/\/doi.org\/10.1007\/978-3-642-18318-8_17.","DOI":"10.1007\/978-3-642-18318-8_17"},{"key":"atypb28","first-page":"285","author":"Parvaresh F.","year":"2005","journal-title":"IEEE"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1997.0439"},{"key":"atypb30","unstructured":"M. Sudan,\n                      \n                        6.897:\n                        Algorithmic Introduction to Coding Theory\n                      \n                      , MIT course on coding theory, Fall 2001,http:\/\/people.seas.harvard.edu\/&#126;madhusudan\/MIT\/FT01\/."},{"key":"atypb31","first-page":"238","author":"Ta-Shma A.","year":"2017","journal-title":"ACM"},{"key":"atypb32","first-page":"126","author":"Trevisan L.","year":"2003","journal-title":"IEEE"},{"key":"atypb33","first-page":"31","author":"Trevisan L.","year":"2005","journal-title":"ACM"},{"key":"atypb34","first-page":"80","author":"Yao A. C.","year":"1982","journal-title":"IEEE"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1276650","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:19:15Z","timestamp":1787339955000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1276650"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1276650"],"URL":"https:\/\/doi.org\/10.1137\/19m1276650","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}