CS 6815: Pseudorandomness and Combinatorial Constructions (Fall 2019)

Instructor: Eshan Chattopadhyay

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

Location: Hollister Hall 368

Office hours: Thursdays, 3-4pm (Gates 319), or by appointment

Piazza: Announcements and discussion

CMS: HW posting and submission

About this course: Random bits are essential in modern computation, with wide ranging applications in areas such as algorithm design, cryptography, and distributed computing. But where do we get random bits from? In cryptography, it is very essential that we use high quality randomness to avoid security breaches! On the flip side, for various randomized algorithms often a deterministic algorithm is discovered (e.g, the problem of testing whether a given number is prime). This leads to the following question: For every efficient randomized algorithm, is there a deterministic counterpart? The focus of this course will be to study such questions.

Prerequisites: We will make the course self contained. Some mathematical maturity is expected. Familiarity with basic notions of algebra (such as finite fields, basics of vector spaces, polynomials), linear algebra, discrete probability, and basics of computational complexity theory will come in handy.

Tentative list of topics


Lecture notes


The main reference for the course will be scribed lecture notes. A link to the Fall'18 edition of this course. Other resources: