Fine Design Seminar Series

Small-bias distributions, introduced by Naor and Naor in 1993, are a fundamental object in pseudorandomness with a striking variety of applications.  In the last ten years several papers have considered taking sum of independent copies.  Some interesting properties have been shown but many others remain unknown.  For example, it is known that such distributions fool low-degree polynomials, and Reingold and Vadhan ask whether they fool one-way logarithmic space computation. In this talk we give two methods to construct examples of small-bias distributions that are *not* fooled by several different computational models.  Either method has the potential to answer RV's question negatively. Joint work with Emanuele Viola.