Dissertation

Seedless Extractors

Goodman, Jesse Patrick McGrenra

2023

Overview

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.

• Publisher: ProQuest Dissertations & Theses
• Subject: Computer Engineering / Computer science / Mathematics
• ISBN: 9798381414400