{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:59:53Z","timestamp":1781078393058,"version":"3.54.1"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,6,16]],"date-time":"2020-06-16T00:00:00Z","timestamp":1592265600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2020,6,16]]},"abstract":"<jats:p>Randomness is a valuable resource in computation. Randomness is used to run various Monte Carlo simulations of complex systems such as the stock market or weather prediction systems. Various randomized algorithms have been discovered that often vastly outperform known deterministic counterparts (see [MR10] for examples). Cryptography is another area that crucially relies on access to random bits, and it is known that various basic cryptographic primitives fail to be secure if the quality of the randomness used is poor [DOPS04]. However natural sources of randomness are typically defective. This leads to the following basic question: \\Can we efficiently produce truly random bits given access to defective sources of randomness?\"<\/jats:p>","DOI":"10.1145\/3406678.3406688","type":"journal-article","created":{"date-parts":[[2020,6,16]],"date-time":"2020-06-16T23:16:02Z","timestamp":1592349362000},"page":"38-57","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Guest Column"],"prefix":"10.1145","volume":"51","author":[{"given":"Eshan","family":"Chattopadhyay","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00359-4"},{"issue":"2","key":"e_1_2_1_2_1","first-page":"145","article-title":"The inuence of large coalitions","volume":"13","author":"Nathan Linial Ajtai","year":"1993","journal-title":"Combinatorica"},{"key":"e_1_2_1_3_1","volume-title":"33rd Computational Complexity Conference (CCC 2018","author":"Ben-Aroya Avraham","year":"2018"},{"key":"e_1_2_1_4_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM","author":"Ben-Aroya Avraham","year":"2019"},{"key":"e_1_2_1_5_1","first-page":"88","volume-title":"Electronic Colloquium on Computational Complexity (ECCC)","volume":"23","author":"Ben-Aroya Avraham","year":"2016"},{"issue":"6","key":"e_1_2_1_6_1","first-page":"1923","article-title":"Generalized privacy ampli_cation","volume":"41","author":"Bennett Charles H","year":"1915","journal-title":"IEEE Transactions on Information Theory"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"[BBR88] Charles H Bennett Gilles Brassard and Jean-Marc Robert. Privacy ampli_cation by public discussion. SIAM journal on Computing 17(2):210{229 1988.  [BBR88] Charles H Bennett Gilles Brassard and Jean-Marc Robert. Privacy ampli_cation by public discussion. SIAM journal on Computing 17(2):210{229 1988.","DOI":"10.1137\/0217014"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447141"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579167"},{"key":"e_1_2_1_10_1","first-page":"416","volume-title":"26th Annual Symposium on Foundations of Com- puter Science (FOCS)","author":"Ben-Or Michael"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1142\/S1793042105000108"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"[Bra10] Mark Braverman. Polylogarithmic independence fools AC0 circuits. Journal of the ACM (JACM) 57(5):1{10 2010.  [Bra10] Mark Braverman. Polylogarithmic independence fools AC0 circuits. Journal of the ACM (JACM) 57(5):1{10 2010.","DOI":"10.1145\/1754399.1754401"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217015"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897547"},{"key":"e_1_2_1_15_1","first-page":"167","volume-title":"2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Chattopadhyay Eshan"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1029837"},{"key":"e_1_2_1_17_1","first-page":"196","volume-title":"2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Cohen Gil"},{"key":"e_1_2_1_18_1","volume-title":"31st Conference on Computational Complexity (CCC 2016","author":"Cohen Gil","year":"2016"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055429"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1096219"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/130908634"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2019.189.3.1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/100783704"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/120868414"},{"key":"e_1_2_1_25_1","first-page":"205","volume-title":"45th Annual IEEE Symposium on Foundations of Computer Science","author":"Dodis Yevgeniy"},{"key":"e_1_2_1_26_1","first-page":"237","volume-title":"48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)","author":"Dziembowski Stefan"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536496"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/090748731"},{"issue":"4","key":"e_1_2_1_29_1","first-page":"294","article-title":"Some remarks on the theory of graphs","volume":"53","author":"P.","year":"1947","journal-title":"Bull. Amer. Math. Soc."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"[GUV09] Venkatesan Guruswami Christopher Umans and Salil Vadhan. Unbalanced expanders and randomness extractors from Parvaresh{Vardy codes. Journal of the ACM (JACM) 56(4):1{34 2009.  [GUV09] Venkatesan Guruswami Christopher Umans and Salil Vadhan. Unbalanced expanders and randomness extractors from Parvaresh{Vardy codes. Journal of the ACM (JACM) 56(4):1{34 2009.","DOI":"10.1145\/1538902.1538904"},{"key":"e_1_2_1_31_1","first-page":"1172","article-title":"On a certain arithmetic sum","volume":"12","author":"Karatsuba A.A.","year":"1971","journal-title":"Soviet Math Dokl."},{"key":"e_1_2_1_32_1","first-page":"545","volume-title":"Doklady Acad. Sci. USSR","volume":"319","author":"Karatsuba AA","year":"1991"},{"key":"e_1_2_1_33_1","volume-title":"Citeseer","author":"Kalai Gil","year":"1989"},{"issue":"4","key":"e_1_2_1_34_1","first-page":"957","article-title":"An explicit two-source extractor with min-entropy rate near 4=9","volume":"65","author":"Lewko Mark","year":"2019","journal-title":"Math- ematika"},{"key":"e_1_2_1_35_1","first-page":"136","volume-title":"2011 IEEE 26th Annual Conference on Computational Complexity","author":"Li Xin"},{"key":"e_1_2_1_36_1","first-page":"109","volume-title":"2013 IEEE 54th Annual Symposium on Foundations of Computer Science","author":"Li Xin"},{"key":"e_1_2_1_37_1","first-page":"531","volume-title":"Theory of Cryptography Conference","author":"Li Xin"},{"key":"e_1_2_1_38_1","first-page":"177","volume-title":"2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Li Xin"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055486"},{"key":"e_1_2_1_40_1","volume-title":"34th Computational Complexity Conference, CCC 2019","author":"Li Xin","year":"2019"},{"key":"e_1_2_1_41_1","first-page":"611","volume-title":"Proceedings of the thirty-_fth annual ACM symposium on Theory of computing","author":"Lu Chi-Jen","year":"2003"},{"key":"e_1_2_1_42_1","first-page":"470","volume-title":"Annual International Cryptology Conference","author":"Maurer Ueli M"},{"key":"e_1_2_1_43_1","first-page":"1148","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Meka Raghu"},{"key":"e_1_2_1_44_1","volume-title":"Chapman & Hall\/CRC","author":"Motwani Rajeev","year":"2010"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00022-3"},{"key":"e_1_2_1_46_1","first-page":"321","volume-title":"Annual International Cryptology Conference","author":"Maurer Ueli"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0004"},{"key":"e_1_2_1_48_1","first-page":"264","article-title":"On a problem of formal logic. Proceedings of the London Mathe- matical Society","volume":"2","author":"Ramsey Frank P.","year":"1930","journal-title":"Series"},{"key":"e_1_2_1_49_1","first-page":"101","volume-title":"2009 24th Annual IEEE Conference on Computational Complexity","author":"Rao Anup"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060593"},{"key":"e_1_2_1_51_1","series-title":"Current Trends in Theoretical Computer Science: The Challenge of the New Century","first-page":"228","volume-title":"Algorithms and Complexity","author":"Shaltiel Ronen"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502099"},{"key":"e_1_2_1_53_1","first-page":"474","volume-title":"40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039)","author":"Umans Christopher"},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","unstructured":"[Vad12] Salil P Vadhan. Pseudorandomness. Foundations and Trends R in Theoretical Com- puter Science 7(1{3):1{336 2012.  [Vad12] Salil P Vadhan. Pseudorandomness. Foundations and Trends R in Theoretical Com- puter Science 7(1{3):1{336 2012.","DOI":"10.1561\/0400000010"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085983X"},{"key":"e_1_2_1_56_1","first-page":"36","article-title":"Various techniques used in connection with random digits","volume":"12","author":"von Neumann J.","year":"1951","journal-title":"Applied Math Series"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167163"},{"key":"e_1_2_1_58_1","first-page":"543","volume-title":"Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science","author":"Zuckerman David"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266407"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132612"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406678.3406688","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406678.3406688","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:36Z","timestamp":1750197696000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406678.3406688"}},"subtitle":["A Recipe for Constructing Two-Source Extractors"],"short-title":[],"issued":{"date-parts":[[2020,6,16]]},"references-count":61,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6,16]]}},"alternative-id":["10.1145\/3406678.3406688"],"URL":"https:\/\/doi.org\/10.1145\/3406678.3406688","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2020,6,16]]},"assertion":[{"value":"2020-06-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}