Fall 2015

Fine Design Seminar Series

Monday, December 7th, 2015, 11:00 am12:30 pm

Add to Calendar

Chin Ho Lee (Northeastern University)

Calvin Lab Room 116

Some Limitations of the Sum of Small-Bias Distributions

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 negativelyJoint work with Emanuele Viola.