Pseudorandom Generators

5 views

Skip to first unread message

Siddhartha Jain

unread,

Feb 15, 2020, 1:53:12 AM2/15/20

to Theory

Hi all,

Pseudorandom Generators for Branching Programs is an important and popular topic in Theoretical Computer Science, a classical result being Nisan's PRG. The motivation is to reduce the expense of generating random bits by "fooling" machines into thinking you are generating n bits by generating only about polylog(n) bits and doing some computation on them.

Nisan's PRG essentially achieves O(log²(n)) bits. It was an open problem for a long time whether restricting the width of the Branching Program to constant could help you get better results. Recently there was a breakthrough result in this direction, which brought this quantity down to almost O(log(n)) for width 3. I wanted to understand this paper, and this will take time and effort so I wanted to schedule meetings over the course of this semester with people who might be interested.

I could cover Nisan's PRG in our first meeting so that the only pre-requisite for joining would be interest and the vague yet ever-present term, mathematical maturity. If you are interested, please let me know by replying to this email.