Talks
Spring 2017

Pseudorandom Generators from Gaussian Processes

Tuesday, June 19th, 2018 2:45 pm3:15 pm

Add to Calendar

We construct new PRGs for intersections (and other functions) of halfspaces over the Gaussian space. In particular, we show that standard derandomizations of the Johnson-Lindenstrauss transforms instantiated with appropriate parameters yields PRGs for these classes. Arguably significantly simpler than previous constructions, these also beat the known state of the art for these classes. (1) For intersections of k-halfspaces with constant error, our seed length is O(log n) + poly(log k). Thus, this remains O(log n) for k = n^{c} for c>0. Previously, this guarantee was known for k = O(log n / log log n). (2) For arbitrary functions, we achieve a seed length of O(log n) + poly(k). This remains O(log n) for k = log n^{c} for c>0. Previously, this guarantee was known for k = O(log log n). Our proof exploits (easy) tools from the theory of Gaussian processes. Joint work with Eshan Chattopadhyay and Rocco Servedio.