Fractional Pseudorandom Generators
2Pooya Hatami (Ohio State University)
https://simons.berkeley.edu/talks/pooya-hatami-ohio-state-university-2023-06-28
Beyond the Boolean Cube
A pseudorandom generator for a family of Boolean functions on the Boolean cube is a procedure that maps a short uniform seed into a vertex of the Boolean cube, in such a way that the expected value of any function in the family, under the uniform distribution, is close to its expected value under the image of the generator.
In this talk, I will discuss a relaxed notion of a pseudorandom generator called a fractional pseudorandom generator, where the image of the generator is allowed to take values in the solid cube. I will then present the polarizing random walks framework that transforms a good fractional pseudorandom generator into a good pseudorandom generator under some reasonable additional assumptions. Finally, I will present recent works that demonstrate how to utilize this framework for constructing pseudorandom generators from various Fourier tail-bound assumptions.