About the course

Randomness plays a crucial role in computer science, along with its applications in fields like cryptography and coding theory. Understanding the extent to which randomness aids computation consists of deep and fundamental questions in complexity theory. Within this context, pseudorandomness is all about comprehending the attributes of randomness that effectively cater to our structural and computational requisites. 

In this course, our attention will be directed towards two primary focal points within pseudorandomness: pseudorandom generators and randomness extractors. We will delve into the study of both classical and contemporary methods for constructing these objects. The techniques will be versatile: combinatorial, probabilistic, algebraic, and (Fourier-)analytic. 

In the initial segment of the course, our focus will be on constructing k-wise independent distributions and small-bias sets. Subsequently, we will proceed to construct remarkably powerful pseudorandom generators that draw upon these foundational constructs for various computational models such as low-degree polynomials, low-depth circuits, and space bounded algorithms. We will then transition to the exploration of randomness extractors, with specific emphasis on seeded extractors and two-source extractors.