Seedless Extractors

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.

Name thesis:degree_name

Ph. D., Computer Science

Level thesis:degree_level

Doctor of Philosophy

Discipline thesis:degree_discipline

Computer Science

Grantor

Cornell University

Year dc:date.issued

2023

Author dc:creator

• Goodman, Jesse

Committee members dc:contributor.committeemember

• Tardos, Eva
• Kleinberg, Robert

• Combinatorics
• Complexity theory
• Explicit constructions
• Lower bounds
• Randomness extractors

Statement dc:rights

• Attribution 4.0 International

Licence dc:rights.uri

• https://creativecommons.org/licenses/by/4.0/

Language dc:language.iso

en

DOI

http://doi.org/10.7298/9f9d-7t34

Dc Identifier Other

ProQuest Submission ID: 14114
ProQuest Publication ID: 30814134

OAI identifier oai:identifier

oai:ecommons.cornell.edu:1813/115687