Speaker: Satyadev Nandakumar

Abstract:
In computational complexity theory, a probability distribution on a
finite set of finite strings is said to be pseudorandom if no
polynomial-size circuit is able to distinguish it from the uniform
distribution on the same set. In this talk, we give an overview of a
recent attempt to apply the theory of effective fractal dimension to
define how close an arbitrary distribution is to being pseudorandom
and relate it to known computational analogues of entropy. We also
study the problem of whether it is possible to extract pseudorandom
bits from a general distribution, analogous to the problem of
extracting random bits from a pseudorandom source.