2026-09-19T06:53:38Zhttps://ecommons.cornell.edu/server/oai/request

oai:ecommons.cornell.edu:1813/1156872026-05-15T19:51:52Zcom_1813_35col_1813_47

Goodman, Jesse Chattopadhyay, Eshan Tardos, Eva Kleinberg, Robert 2024-10-16T20:19:16Z 2024-10-16T20:19:16Z 2023-12 ProQuest Submission ID: 14114 ProQuest Publication ID: 30814134 https://hdl.handle.net/1813/115687 http://doi.org/10.7298/9f9d-7t34 16454735 493 pages Randomness is a powerful tool, exploited almost everywhere in computer science – from cryptography, to distributed computing, to algorithm design and more. Unfortunately, most of these applications require access to perfectly uniform bits, while randomness harvested from nature (e.g., atmospheric noise, radioactive decay, other quantum phenomena) rarely looks so pure. This motivates the study of randomness extractors, which are deterministic algorithms that convert weak sources of randomness into uniformly random bits. The study of extractors dates back over 70 years, and has blossomed into a beautiful theory with deep connections to cryptography, complexity theory, and combinatorics. As it is impossible to construct a single extractor that works for all weak sources of randomness, research on extractors has split into two complementary settings: (1) the seeded setting, where the extractor is equipped with a short uniform seed to help extract bits from the weak source; and (2) the seedless setting, where the extractor is given no seed, but the weak source is equipped with some additional structure. While a rich body of work has culminated in near-optimal seeded extractors, we are still far from constructing optimal seedless extractors. In this thesis, we explicitly construct new seedless extractors that significantly improve the previous state-of-the-art. To build our extractors, we exploit new reductions within pseudorandomness, and unearth new connections to extremal combinatorics, communication complexity, and coding theory. Along the way, we unlock exciting new applications in cryptography, complexity theory, and beyond. en Attribution 4.0 International https://creativecommons.org/licenses/by/4.0/ Combinatorics Complexity theory Explicit constructions Lower bounds Randomness extractors Seedless Extractors dissertation or thesis https://newcatalog.library.cornell.edu/catalog/16454735 application/pdf Computer Science Cornell University Doctor of Philosophy Ph. D., Computer Science https://hdl.handle.net/1813/59810.2 Publication Cornell Theses and Dissertations Goodman, Jesse 5893a6ea-7af3-41d7-abc6-04bcd26ab5df open.access open.access <Publication xmlns="https://www.openaire.eu/cerif-profile/1.1/" id="0cef039d-a218-4c4f-8c1d-8a3a4b3ceed9"> <Type xmlns="https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types">http://purl.org/coar/resource_type/c_1843</Type> <Language>en</Language> <Title>Seedless Extractors</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2023-12</PublicationDate> <DOI>http://doi.org/10.7298/9f9d-7t34</DOI> <Authors> <Author> <DisplayName>Goodman, Jesse</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <License>https://creativecommons.org/licenses/by/4.0/</License> <Keyword>Combinatorics</Keyword> <Keyword>Complexity theory</Keyword> <Keyword>Explicit constructions</Keyword> <Keyword>Lower bounds</Keyword> <Keyword>Randomness extractors</Keyword> <Abstract>Randomness is a powerful tool, exploited almost everywhere in computer science – from cryptography, to distributed computing, to algorithm design and more. Unfortunately, most of these applications require access to perfectly uniform bits, while randomness harvested from nature (e.g., atmospheric noise, radioactive decay, other quantum phenomena) rarely looks so pure. This motivates the study of randomness extractors, which are deterministic algorithms that convert weak sources of randomness into uniformly random bits. The study of extractors dates back over 70 years, and has blossomed into a beautiful theory with deep connections to cryptography, complexity theory, and combinatorics. As it is impossible to construct a single extractor that works for all weak sources of randomness, research on extractors has split into two complementary settings: (1) the seeded setting, where the extractor is equipped with a short uniform seed to help extract bits from the weak source; and (2) the seedless setting, where the extractor is given no seed, but the weak source is equipped with some additional structure. While a rich body of work has culminated in near-optimal seeded extractors, we are still far from constructing optimal seedless extractors. In this thesis, we explicitly construct new seedless extractors that significantly improve the previous state-of-the-art. To build our extractors, we exploit new reductions within pseudorandomness, and unearth new connections to extremal combinatorics, communication complexity, and coding theory. Along the way, we unlock exciting new applications in cryptography, complexity theory, and beyond.</Abstract> <Access xmlns="http://purl.org/coar/access_right" > </Access> </Publication>