{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:00:51Z","timestamp":1760238051369,"version":"build-2065373602"},"reference-count":67,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2022,6,26]],"date-time":"2022-06-26T00:00:00Z","timestamp":1656201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF CAREER Award","doi-asserted-by":"publisher","award":["2045576"],"award-info":[{"award-number":["2045576"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The area of randomness extraction has seen interesting advances in recent years, with rapid progress on many longstanding open problems, along with the introduction of many new notions that played a key role in this development. We survey this progress and highlight new definitions and notions that have been the subject of intense study in recent work.<\/jats:p>","DOI":"10.3390\/e24070880","type":"journal-article","created":{"date-parts":[[2022,6,26]],"date-time":"2022-06-26T09:00:13Z","timestamp":1656234013000},"page":"880","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Recent Advances in Randomness Extraction"],"prefix":"10.3390","volume":"24","author":[{"given":"Eshan","family":"Chattopadhyay","sequence":"first","affiliation":[{"name":"Department of Computer Science, Cornell University, Ithaca, NY 14850, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,6,26]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Motwani, R., and Raghavan, P. (2010). Randomized Algorithms, Chapman & Hall\/CRC.","DOI":"10.1201\/9781584888239-c12"},{"key":"ref_2","unstructured":"Dodis, Y., Ong, S.J., Prabhakaran, M., and Sahai, A. (2004, January 17\u201319). On the (im)possibility of cryptography with imperfect randomness. Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","article-title":"Hardness vs randomness","volume":"49","author":"Nisan","year":"1994","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., and Wigderson, A. (1997, January 4\u20136). P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, El Paso, TX, USA.","DOI":"10.1145\/258533.258590"},{"key":"ref_5","unstructured":"Wikipedia (2022, June 03). Hardware Random Number Generator\u2014Wikipedia, The Free Encyclopedia. Available online: http:\/\/en.wikipedia.org\/w\/index.php?title=Hardware%20random%20number%20generator&oldid=1088716271."},{"key":"ref_6","first-page":"36","article-title":"Various Techniques Used in Connection with Random Digits","volume":"12","year":"1951","journal-title":"Appl. Math Ser."},{"key":"ref_7","first-page":"1","article-title":"The Intel random number generator","volume":"27","author":"Jun","year":"1999","journal-title":"Cryptogr. Res. Inc. White Pap."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"33740","DOI":"10.1038\/srep33740","article-title":"True randomness from big data","volume":"6","author":"Papakonstantinou","year":"2016","journal-title":"Sci. Rep."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1137\/0217015","article-title":"Unbiased bits from sources of weak randomness and probabilistic communication complexity","volume":"17","author":"Chor","year":"1988","journal-title":"SIAM J. Comput."},{"key":"ref_10","unstructured":"Zuckerman, D. (1990, January 22\u201324). General weak random sources. Proceedings of the 1990 31st Annual Symposium on Foundations of Computer Science, St. Louis, MO, USA."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1006\/jcss.1996.0004","article-title":"Randomness is linear in space","volume":"52","author":"Nisan","year":"1996","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Lu, C.J., Reingold, O., Vadhan, S., and Wigderson, A. (2003, January 9\u201311). Extractors: Optimal up to constant factors. Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, San Diego, CA, USA.","DOI":"10.1145\/780542.780630"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1538902.1538904","article-title":"Unbalanced expanders and randomness extractors from Parvaresh\u2013Vardy codes","volume":"56","author":"Guruswami","year":"2009","journal-title":"JACM"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2305","DOI":"10.1137\/100783704","article-title":"Extensions to the method of multiplicities, with applications to Kakeya sets and mergers","volume":"42","author":"Dvir","year":"2013","journal-title":"SIAM J. Comput."},{"key":"ref_15","unstructured":"Dodis, Y., and Wichs, D. (June, January 31). Non-malleable extractors and symmetric key cryptography from weak secrets. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, Bethesda, MD, USA."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1137\/0217014","article-title":"Privacy amplification by public discussion","volume":"17","author":"Bennett","year":"1988","journal-title":"SIAM J. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1915","DOI":"10.1109\/18.476316","article-title":"Generalized privacy amplification","volume":"41","author":"Bennett","year":"1995","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_18","unstructured":"Maurer, U.M. (1992). Protocols for secret key agreement by public discussion based on common information. Annual International Cryptology Conference, Springer."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Maurer, U., and Wolf, S. (1997). Privacy amplification secure against active adversaries. Annual International Cryptology Conference, Springer.","DOI":"10.1007\/BFb0052244"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Cheraghchi, M., and Guruswami, V. (2014). Non-malleable coding against bit-wise and split-state tampering. Theory of Cryptography Conference, Springer.","DOI":"10.1007\/978-3-642-54242-8_19"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3178432","article-title":"Non-malleable codes","volume":"65","author":"Dziembowski","year":"2018","journal-title":"JACM"},{"key":"ref_22","unstructured":"Ben-Aroya, A., Doron, D., and Ta-Shma, A. (2016). Explicit Two-Source Extractors for Near-Logarithmic Min-Entropy, Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Chattopadhyay, E., and Li, X. (2016, January 9\u201311). Explicit non-malleable extractors, multi-source extractors, and almost optimal privacy amplification protocols. Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), New Brunswick, NJ, USA.","DOI":"10.1109\/FOCS.2016.25"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Cohen, G. (2016, January 9\u201311). Making the most of advice: New correlation breakers and their applications. Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), New Brunswick, NJ, USA.","DOI":"10.1109\/FOCS.2016.28"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Meka, R. (2017, January 16\u201319). Explicit resilient functions matching Ajtai-Linial. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain.","DOI":"10.1137\/1.9781611974782.73"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Cohen, G. (2017, January 19\u201323). Towards optimal two-source extractors and Ramsey graphs. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, Montreal, PQ, Canada.","DOI":"10.1145\/3055399.3055429"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Li, X. (2017, January 19\u201323). Improved non-malleable extractors, non-malleable codes and independent source extractors. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, Montreal, PQ, Canada.","DOI":"10.1145\/3055399.3055486"},{"key":"ref_28","unstructured":"Li, X. (2019, January 18\u201320). Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions. Proceedings of the 34th Computational Complexity Conference, New Brunswick, NJ, USA."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1231","DOI":"10.1137\/S0097539705446846","article-title":"Deterministic extractors for bit-fixing sources and exposure-resilient cryptography","volume":"36","author":"Kamp","year":"2007","journal-title":"SIAM J. Comput."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Rao, A. (2009, January 15\u201318). Extractors for low-weight affine sources. Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, Paris, France.","DOI":"10.1109\/CCC.2009.36"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Find, M.G., Golovnev, A., Hirsch, E.A., and Kulikov, A.S. (2016, January 9\u201311). A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function. Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS, New Brunswick, NJ, USA.","DOI":"10.1109\/FOCS.2016.19"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1007\/s00493-008-2259-3","article-title":"Deterministic extractors for affine sources over large fields","volume":"28","author":"Gabizon","year":"2008","journal-title":"Combinatorica"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s00039-007-0593-z","article-title":"On the construction of affine extractors","volume":"17","author":"Bourgain","year":"2007","journal-title":"GAFA Geom. Funct. Anal."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s00493-011-2604-9","article-title":"Affine extractors over prime fields","volume":"31","author":"Yehudayoff","year":"2011","journal-title":"Combinatorica"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Li, X. (2011, January 8\u201310). A New Approach to Affine Extractors and Dispersers. Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, CA, USA.","DOI":"10.1109\/CCC.2011.27"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Li, X. (2016, January 9\u201311). Improved two-source extractors, and affine extractors for polylogarithmic entropy. Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, New Brunswick, NJ, USA.","DOI":"10.1109\/FOCS.2016.26"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Chattopadhyay, E., Goodman, J., and Liao, J. (2022, January 7\u201310). Affine Extractors for Almost Logarithmic Entropy. Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, Denver, CO, USA.","DOI":"10.1109\/FOCS52979.2021.00067"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Chattopadhyay, E., and Liao, J. (2022, January 20\u201324). Extractors for Sum of Two Sources. Proceedings of the STOC \u201922: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy.","DOI":"10.1145\/3519935.3519963"},{"key":"ref_39","unstructured":"Trevisan, L., and Vadhan, S. (2000, January 12\u201314). Extracting randomness from samplable distributions. Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.jcss.2010.06.014","article-title":"Deterministic extractors for small-space sources","volume":"77","author":"Kamp","year":"2011","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1137\/11085983X","article-title":"Extractors for circuit sources","volume":"43","author":"Viola","year":"2014","journal-title":"SIAM J. Comput."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Chattopadhyay, E., and Li, X. (2016, January 19\u201321). Extractors for Sumset Sources. Proceedings of the STOC \u201916: Symposium on Theory of Computing, Cambridge, MA, USA.","DOI":"10.1145\/2897518.2897643"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Chattopadhyay, E., and Goodman, J. (2022, January 7\u201310). Improved Extractors for Small-Space Sources. Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, Denver, CO, USA.","DOI":"10.1109\/FOCS52979.2021.00066"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1137\/120868414","article-title":"Privacy amplification and nonmalleable extractors via character sums","volume":"43","author":"Dodis","year":"2014","journal-title":"SIAM J. Comput."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1137\/130908634","article-title":"Nonmalleable extractors with short seeds and applications to privacy amplification","volume":"43","author":"Cohen","year":"2014","journal-title":"SIAM J. Comput."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Li, X. (2012, January 20\u201323). Non-malleable extractors, two-source extractors and privacy amplification. Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, Washington, DC, USA.","DOI":"10.1109\/FOCS.2012.26"},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Chattopadhyay, E., Goyal, V., and Li, X. (2016, January 19\u201321). Non-malleable extractors and codes, with their many tampered extensions. Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, Cambridge, MA, USA.","DOI":"10.1145\/2897518.2897547"},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Li, X. (2013, January 26\u201329). Extractors for a constant number of independent sources with polylogarithmic min-entropy. Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2013.19"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1137\/15M1029837","article-title":"Local correlation breakers and applications to three-source extractors and mergers","volume":"45","author":"Cohen","year":"2016","journal-title":"SIAM J. Comput."},{"key":"ref_50","unstructured":"Cohen, G. (June, January 29). Non-malleable extractors\u2014New tools and improved constructions. Proceedings of the 31st Conference on Computational Complexity (CCC 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Tokyo, Japan."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Dziembowski, S., and Pietrzak, K. (2007, January 21\u201323). Intrusion-resilient secret sharing. Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201907), IEEE, Washington, DC, USA.","DOI":"10.1109\/FOCS.2007.63"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1145\/3406678.3406688","article-title":"Guest Column: A Recipe for Constructing Two-Source Extractors","volume":"51","author":"Chattopadhyay","year":"2020","journal-title":"SIGACT News"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z","article-title":"Randomness-optimal oblivious sampling","volume":"11","author":"Zuckerman","year":"1997","journal-title":"Random Struct. Algorithms"},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S1793042105000108","article-title":"More on the sum-product phenomenon in prime fields and its applications","volume":"1","author":"Bourgain","year":"2005","journal-title":"Int. J. Number Theory"},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"653","DOI":"10.4007\/annals.2019.189.3.1","article-title":"Explicit two-source extractors and resilient functions","volume":"189","author":"Chattopadhyay","year":"2019","journal-title":"Ann. Math."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"1095","DOI":"10.1137\/S0097539705447141","article-title":"Extracting randomness using few independent sources","volume":"36","author":"Barak","year":"2006","journal-title":"SIAM J. Comput."},{"key":"ref_57","doi-asserted-by":"crossref","unstructured":"Li, X. (2011, January 8\u201311). Improved constructions of three source extractors. Proceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity, San Jose, CA, USA.","DOI":"10.1109\/CCC.2011.26"},{"key":"ref_58","doi-asserted-by":"crossref","unstructured":"Li, X. (2015, January 17\u201320). Three-source extractors for polylogarithmic min-entropy. Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, Berkeley, CA, USA.","DOI":"10.1109\/FOCS.2015.58"},{"key":"ref_59","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., and Linial, N. (1985, January 21\u201323). Collective coin flipping, robust voting schemes and minima of Banzhaf values. Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS), Portland, OR, USA.","DOI":"10.1109\/SFCS.1985.15"},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF01303199","article-title":"The influence of large coalitions","volume":"13","author":"Ajtai","year":"1993","journal-title":"Combinatorica"},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1754399.1754401","article-title":"Polylogarithmic independence fools AC0 circuits","volume":"57","author":"Braverman","year":"2010","journal-title":"JACM"},{"key":"ref_62","unstructured":"Ben-Aroya, A., Chattopadhyay, E., Doron, D., Li, X., and Ta-Shma, A. (2018, January 22\u201324). A new approach for constructing low-error, two-source extractors. Proceedings of the 33rd Computational Complexity Conference (CCC 2018), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, San Diego, CA, USA."},{"key":"ref_63","first-page":"1156","article-title":"How to Extract Useful Randomness from Unreliable Sources","volume":"2019","author":"Aggarwal","year":"2019","journal-title":"IACR Cryptol. EPrint Arch."},{"key":"ref_64","first-page":"183","article-title":"Randomness Extraction from Somewhat Dependent Sources","volume":"26","author":"Ball","year":"2019","journal-title":"Electron. Colloq. Comput. Complex."},{"key":"ref_65","doi-asserted-by":"crossref","unstructured":"Chattopadhyay, E., Goodman, J., Goyal, V., and Li, X. (2020, January 22\u201326). Extractors for adversarial sources via extremal hypergraphs. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, Online.","DOI":"10.1145\/3357713.3384339"},{"key":"ref_66","first-page":"60","article-title":"Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols","volume":"27","author":"Chattopadhyay","year":"2020","journal-title":"Colloq. Comput. Complex."},{"key":"ref_67","doi-asserted-by":"crossref","unstructured":"Kahn, J., Kalai, G., and Linial, N. (1988, January 24\u201326). The Influence of Variables on Boolean Functions. Proceedings of the 29th Annual Symposium on Foundations of Computer Science, White Plains, NY, USA.","DOI":"10.1109\/SFCS.1988.21923"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/7\/880\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:38:39Z","timestamp":1760139519000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/7\/880"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,26]]},"references-count":67,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2022,7]]}},"alternative-id":["e24070880"],"URL":"https:\/\/doi.org\/10.3390\/e24070880","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2022,6,26]]}}}