AF:Small:New Directions in Randomness Extraction

About This Grant

Randomness is a fundamental resource in modern computation, with critical applications in securing internet communication, executing machine learning algorithms, and simulating complex systems such as financial markets and physical processes. However, high-quality random bits are difficult to obtain from natural sources. The area of randomness extraction is a systematic study of defective sources of randomness found in nature and devising efficient algorithms that provably generate high-quality randomness that are critical for above mentioned applications. Pushing the frontiers of this line of research is the main goal of this proposal. The outcomes of this work will improve the security of everyday online systems, enhance the performance of randomized algorithms, and support more accurate simulations across science and engineering. The outcomes of this work will support secure digital infrastructure, advance science and technology, and enhance economic resilience. The field of randomness extraction has seen major success over the past decade, with powerful constructions and deep connections across theoretical computer science. This project builds on that foundation by exploring new models of defective randomness sources that go beyond the traditional assumption of independence. These include sources with correlations, dependencies, or structural limitations that naturally arise in practice. The project investigates efficient algorithms that can extract or condense randomness in these more realistic scenarios, with applications in areas such as leakage-resilient cryptography, fault-tolerant distributed computing, communication complexity, and circuit lower bounds. A complementary goal is to construct extractors with extremely low error rates, a key requirement for cryptographic applications, which remains a central open problem despite substantial progress. Together, these directions represent key directions in advancing both the theory and practical relevance of randomness extraction. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.