Bounded independence plus noise and derandomization
Host
Noah Golowich
MIT
Abstract:
k-wise independent distributions have been a fundamental object in algorithm design and derandomization since the late 70s. They are defined as distributions on n bits that are uniform on every k coordinates. Despite their importance, they have limitations as a pseudorandom object. A recent line of work has shown that adding noise to k-wise independent distributions can be unexpectedly powerful, leading to new constructions of pseudorandom generators (PRGs) for various classes of functions. In this talk, I will present an overview of the latest research on the topic, including various constructions and analyses of PRGs, and how it is related to coding theory and Boolean function analysis.
k-wise independent distributions have been a fundamental object in algorithm design and derandomization since the late 70s. They are defined as distributions on n bits that are uniform on every k coordinates. Despite their importance, they have limitations as a pseudorandom object. A recent line of work has shown that adding noise to k-wise independent distributions can be unexpectedly powerful, leading to new constructions of pseudorandom generators (PRGs) for various classes of functions. In this talk, I will present an overview of the latest research on the topic, including various constructions and analyses of PRGs, and how it is related to coding theory and Boolean function analysis.