AF: Small: Challenges in Unconditional Pseudorandomness for Boolean Computation

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

The performance of modern computers can be measured on several axes, such as the time or memory consumed. Another axis is the amount of randomness used, as many common algorithms (such as opinion polls) use randomness as a key resource. However, true randomness (such as that derived from physical phenomena) can be a scarce resource, and as such significant research has explored how the use of randomness can be minimized while still efficiently solving key algorithmic problems. One prominent algorithmic challenge is to compute the volume of geometric objects. While this problem is simple in low dimensions, it is significantly more difficult in the higher number of dimensions often required for applications. While randomized algorithms have been developed for (approximately) computing volumes, comparable deterministic algorithms have yet to be developed. This project will study techniques for the design of such algorithms. It will also promote the study of pseudorandomness in general through course design, organization of workshops, and training of undergraduate and graduate students. In particular, this project will design pseudorandom generators, which are maps that stretch a short seed of (true) randomness to a longer output of pseudorandomness, where this output is indistinguishable from random (from the perspective of the relevant algorithm). The construction of suitable pseudorandom generators is a well-known avenue to the derandomization of algorithms. However, existing constructions of pseudorandom generators fall short of derandomization even for simple algorithmic problems. This project will study new paradigms for the construction of pseudorandom generators, especially for those which can derandomize algorithms for geometric problems such as (approximately) computing volumes. This study will be facilitated by combining existing tools, such as those from communication complexity and cryptographic pseudorandomness, in novel ways. 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.