CS 6815: Pseudorandomness and Combinatorial Constructions (Fall 2022)

Instructor: Eshan Chattopadhyay

Class schedule: TR 9:40-10:55am

Location: Hollister Hall 401

Office hours: Mondays, 2:30-3:30pm (Gates 319), or by appointment

Logistics: We will use Ed for announcements/discussion and Canvas for 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: Any of CS 4810, CS 4820 or CS 4814; or permission of instructor. In general, some mathematical maturity is expected. Familiarity with basic notions of algebra (such as finite fields, basics of vector spaces, polynomials), linear algebra, and discrete probability will come in handy.

Tentative list of topics

Grading: Performance in this course will be evaluated as follows:


The main reference for the course will be scribed lecture notes. The following are some very useful resources: Here is a link to the Fall'19 edition of this course. Additional resources are listed below.  

Lecture notes

(will be updated as the semester progresses)


You should expect and demand to be treated by your classmates and the course staff with respect. You belong here, and we are here to help you learn and enjoy this course. If any incident occurs that challenges this commitment to a supportive and inclusive environment, please let the instructors know so that the issue can be addressed. We are personally committed to this, and subscribe to the Computer Science Department's Values of Inclusion.

Additional Resources

Similar courses taught before: Books/Surverys/Notes: Video lectures: