Randomness in Computation
Many areas of computation, including algorithm design, cryptography, and distributed computing, rely heavily on randomized techniques. When randomness is understood to be essential, as in cryptography, applications are typically thought to require true randomness. Natural sources of randomness, such as radio noise, are typically defective, however, and our ability to generate true, high-quality randomness is limited. In algorithm design, by contrast, it's not even clear that randomness is fundamentally required. Despite the ubiquitous use of randomness in computation, key questions about the power of randomness and when randomness is required remain unanswered.
With this CAREER award, Eshan Chattopadhyay, Computer Science, is advancing understandings of randomness in computation by pursuing two complementary lines of research. The first, investigating unconditional de-randomization, seeks to advance the state of the art in areas such as 1) unconditionally derandomizing algorithms that use limited memory, and 2) various circuit families that are currently beyond reach. This research direction will leverage new approaches that exploit Fourier analytic structure and novel frameworks of de-randomization based on fractional pseudorandom generators and pseudorandom pseudo-distributions. The second line of research focuses on extracting purely random bits from low-quality sources of randomness that occur in nature. This project will also explore the use of such extractors in the unconditional de-randomization pursued in the first line of research.
This research will address outstanding questions in complexity theory. Goals include constructing better extractors of randomness in the presence of adversaries—an aim with important applications in cryptography.