Home > Teaching > CS 744: Pseudo-Random Generators

CS 744: Pseudo-Random Generators

Departments to which the proposed course will be of interest:

CSE, Maths


Course Contents:

Pseudo-random generators are efficiently computable functions that stretch an input random string to a much bigger sized string such that the output string appears random to resource-bounded computations. These functions have become one of the fundamental objects to study in complexity theory because of their utility. They are used to derandomize randomized algorithms, formalize notions of cryptographic security, obtain lower bounds on the complexity of problems etc. (unfortunately, as of now very few constructions of pseudo- random generators are provably known although many are conjectured). In this course, we study pseudo-random generators and their connections in depth.


The topics covered in the course are as follows: