Personal tools
You are here: Home Graduate Study Topics in Pseudorandomness and Circuit Lower Bounds

Topics in Pseudorandomness and Circuit Lower Bounds

This topic is suitable for a student with interests in cryptography or complexity theory.

Pseudorandom generators are functions whose output is indistinguishable from random by a computationally bounded adversary. The theory of pseudorandomness formalizes these objects and studies the conditions under which they can be constrcuted, and is strongly linked to the fundamental question of finding explicit functions without small Boolean circuits. Furthermore, there are connections to a number of other areas, such as coding theory, graph theory and even harmonic analysis! 

Though there's been a lot of work in building up this theory over the past couple of decades, a number of interesting questions remain open. One possible topic is to tighten the connection between derandomization and circuit lower bounds, by showing that any separation of probabilistic polynomial time and deterministic exponential time would lead to circuit lower bounds. Another possibility is to study pseudorandom generators against restricted classes of circuits, like constant-depth circuits with Parity gates. A third possibility, and one that allows the student a good deal of flexibility, is to study stronger notions of pseudorandomness or pseudorandomness in other contexts such as in proof complexity or parameterized complexity.

Prospective Supervisors

Rahul Santhanam

Document Actions