CS 6815: Pseudorandomness and Combinatorial Constructions (Fall 2018)

Instructor: Eshan Chattopadhyay

Class schedule: Tuesdays and Thursdays, 10:10-11:25am

Location: Bard Hall 140

Office hours: 10:30-11:30am on Mondays, Location: Gates 319

About this course: Randomized techniques are prevalent in various areas of computer science including algorithms, distributed computing, cryptography, and stochastic simulations of complex systems. This course aims to explore various fundamental questions related to the use of randomness: Can we find an efficient deterministic algorithm for every problem which can be efficiently solved using a randomized algorithm? Can the use of randomness help in saving memory requirements of algorithms? Can we simulate randomized algorithms having access to imperfect sources of randomness (which are our typical sources of randomness)? Can we produce purely random bits from defective sources of randomness?

As we shall see in this course, Pseudorandomness is a beautiful theory developed to answer many such questions. This will also lead us to various notions of what it is for a deterministic object to be considered random-like. Some key characters that will feature include expander graphs, pseudorandom generators, randomness extractors and error-correcting codes. The course is intended to be a graduate level introduction to this active area of research.

Prerequisites: Familiarity with some Algebra (e.g., finite fields, vector spaces), Linear Algebra, and Discrete Probability. See Resources below for some review material.

Tentative list of topics

Lecture notes


The main reference for the course will be scribed lecture notes. Here are pointers to other useful resources. More stuff will be added as the course progresses.

An excellent reference for this course is the following book. Similar courses taught before: Books/Surverys/Notes: Video lectures:

Few final projects