{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:38Z","timestamp":1750309478173,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":46,"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:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1705028, CCF-2200956, CCF-2008076"],"award-info":[{"award-number":["CCF-1705028, CCF-2200956, CCF-2008076"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100017637","name":"Simons Institute for the Theory of Computing, University of California Berkeley","doi-asserted-by":"publisher","award":["Investigator Award #409864"],"award-info":[{"award-number":["Investigator Award #409864"]}],"id":[{"id":"10.13039\/100017637","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.3585134","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1-9","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Almost Chor-Goldreich Sources and Adversarial Random Walks"],"prefix":"10.1145","author":[{"given":"Dean","family":"Doron","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negev, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Moshkovitz","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Justin","family":"Oh","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Zuckerman","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"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\/SFCS.2002.1181884"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3317691"},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS).","author":"Ball Marshall","year":"2022","unstructured":"Marshall Ball , Oded Goldreich , and Tal Malkin . 2022 . Randomness extraction from somewhat dependent sources . In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS). Marshall Ball, Oded Goldreich, and Tal Malkin. 2022. Randomness extraction from somewhat dependent sources. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22792-9_1"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1734213.1734214"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1027206"},{"key":"e_1_3_2_1_7_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM","author":"Ben-Aroya Avraham","year":"2019","unstructured":"Avraham Ben-Aroya , Gil Cohen , Dean Doron , and Amnon Ta-Shma . 2019. Two-source condensers with low error and small entropy gap via entropy-resilient functions . In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2019 ). Avraham Ben-Aroya, Gil Cohen, Dean Doron, and Amnon Ta-Shma. 2019. Two-source condensers with low error and small entropy gap via entropy-resilient functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2019)."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Avraham Ben-Aroya Dean Doron and Amnon Ta-Shma. 2019. An efficient reduction from two-source to nonmalleable extractors: achieving near-logarithmic min-entropy. SIAM J. Comput. STOC17\u201331. \t\t\t\t  Avraham Ben-Aroya Dean Doron and Amnon Ta-Shma. 2019. An efficient reduction from two-source to nonmalleable extractors: achieving near-logarithmic min-entropy. SIAM J. Comput. STOC17\u201331.","DOI":"10.1137\/17M1133245"},{"volume-title":"Proceedings of the 46th Annual Allerton Conference on Communication, Control, and Computing. 798\u2013805","author":"Berinde Radu","key":"e_1_3_2_1_9_1","unstructured":"Radu Berinde , Anna C. Gilbert , Piotr Indyk , Howard Karloff , and Martin J. Strauss . 2008. Combining geometry and combinatorics: A unified approach to sparse signal recovery . In Proceedings of the 46th Annual Allerton Conference on Communication, Control, and Computing. 798\u2013805 . Radu Berinde, Anna C. Gilbert, Piotr Indyk, Howard Karloff, and Martin J. Strauss. 2008. Combining geometry and combinatorics: A unified approach to sparse signal recovery. In Proceedings of the 46th Annual Allerton Conference on Communication, Control, and Computing. 798\u2013805."},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of the 34th Annual Symposium on Theory of Computing (STOC). ACM, 659\u2013668","author":"Capalbo Michael","year":"2002","unstructured":"Michael Capalbo , Omer Reingold , Salil Vadhan , and Avi Wigderson . 2002 . Randomness conductors and constant-degree lossless expanders . In Proceedings of the 34th Annual Symposium on Theory of Computing (STOC). ACM, 659\u2013668 . Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson. 2002. Randomness conductors and constant-degree lossless expanders. In Proceedings of the 34th Annual Symposium on Theory of Computing (STOC). ACM, 659\u2013668."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00066"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00067"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451059"},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS).","author":"Chen Xue","year":"2022","unstructured":"Xue Chen , Kuan Cheng , Xin Li , and Minghui Ouyang . 2022 . Improved Decoding of Expander Codes . In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS). Xue Chen, Kuan Cheng, Xin Li, and Minghui Ouyang. 2022. Improved Decoding of Expander Codes. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS)."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217015"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2141938.2141941"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Domingos Dellamonica  Jr. and Yoshiharu Kohayakawa. 2008. An algorithmic Friedman\u2013Pippenger theorem on tree embeddings and applications. The Electronic Journal of Combinatorics R127\u2013R127. \t\t\t\t  Domingos Dellamonica Jr. and Yoshiharu Kohayakawa. 2008. An algorithmic Friedman\u2013Pippenger theorem on tree embeddings and applications. The Electronic Journal of Combinatorics R127\u2013R127.","DOI":"10.37236\/851"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-84259-8_19"},{"key":"e_1_3_2_1_19_1","volume-title":"Proceedings of the 2nd Conference on Information-Theoretic Cryptography (ITC).","author":"Dodis Yevgeniy","year":"2021","unstructured":"Yevgeniy Dodis , Siyao Guo , Noah Stephens-Davidowitz , and Zhiye Xie . 2021 . Online linear extractors for independent sources . In Proceedings of the 2nd Conference on Information-Theoretic Cryptography (ITC). Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, and Zhiye Xie. 2021. Online linear extractors for independent sources. In Proceedings of the 2nd Conference on Information-Theoretic Cryptography (ITC)."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55220-5_6"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_35"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_1"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00102"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Dean Doron Dana Moshkovitz Justin Oh and David Zuckerman. 2022. Almost Chor\u2013Goldreich Sources and Adversarial Random Walks. In Electronic Colloquium on Computational Complexity (ECCC). \t\t\t\t  Dean Doron Dana Moshkovitz Justin Oh and David Zuckerman. 2022. Almost Chor\u2013Goldreich Sources and Adversarial Random Walks. In Electronic Colloquium on Computational Complexity (ECCC).","DOI":"10.1145\/3564246.3585134"},{"key":"e_1_3_2_1_25_1","volume-title":"Extractors for varieties. computational complexity, 21, 4","author":"Dvir Zeev","year":"2012","unstructured":"Zeev Dvir . 2012. Extractors for varieties. computational complexity, 21, 4 ( 2012 ), 515\u2013572. Zeev Dvir. 2012. Extractors for varieties. computational complexity, 21, 4 (2012), 515\u2013572."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-020-09975-8"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1999.766262"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/280032.280034"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538904"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132613"},{"key":"e_1_3_2_1_31_1","unstructured":"Ting-Chun Lin and Min-Hsiu Hsieh. 2022. Good quantum LDPC codes with linear time decoder from lossless expanders. arXiv preprint arXiv:2203.03581. \t\t\t\t  Ting-Chun Lin and Min-Hsiu Hsieh. 2022. Good quantum LDPC codes with linear time decoder from lossless expanders. arXiv preprint arXiv:2203.03581."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780630"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0004"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197329508"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301294"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703431032"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.2307\/3062153"},{"key":"e_1_3_2_1_38_1","unstructured":"Omer Reingold Salil Vadhan and Avi Wigderson. 2004. A note on extracting randomness from Santha-Vazirani sources. Manuscript. In Electronic Colloquium on Computational Complexity (ECCC). \t\t\t\t  Omer Reingold Salil Vadhan and Avi Wigderson. 2004. A note on extracting randomness from Santha-Vazirani sources. Manuscript. In Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90044-9"},{"key":"e_1_3_2_1_40_1","volume-title":"Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS).","author":"Shaltiel Ronen","year":"2022","unstructured":"Ronen Shaltiel and Emanuele Viola . 2022 . On Hardness Assumptions Needed for \u201cExtreme High-End\u201d PRGs and Fast Derandomization . In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS). Ronen Shaltiel and Emanuele Viola. 2022. On Hardness Assumptions Needed for \u201cExtreme High-End\u201d PRGs and Fast Derandomization. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS)."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979630091X"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0053-2"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892063"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085983X"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89574"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Orlando FL USA","acronym":"STOC '23"},"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.3585134","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585134","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585134","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.3585134"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":46,"alternative-id":["10.1145\/3564246.3585134","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585134","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"}}]}}