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
- Introduction and key pseudorandom objects: Will include introduction to simple pseudorandom distributions (such as k-wise independent distributions and small-biased distributions), hash functions, error correcting codes, and expander graphs.
- Producing truly random bits from imperfect sources and applications: This topic will be studied in depth, with the key notion being that of a randomness extractor. We will study seeded extractors, non-malleable extractors, extractors for independent sources. We will see applications to combinatorics (to objects known as Ramsey graphs) and to cryptography.
- Derandomization: A basic question in computational complexity theory is whether randomness is essential for efficient computation, i.e., can using random bits significantly reduce the running time (or amount of memory) used by algorithms. We will study these questions in detail.
Grading: Performance in this course will be evaluated as follows:
- Scribe notes: 30%. You are expected to scribe at least 2 lectures (this might change depending on enrollment). You will be required to send in an initial draft of the scribed notes by 48 hours after the lecture.
Here is template
that you can use.
- Homeworks: 25%. There will be 3 homework assignments well spread in the semester. Solving problems will require original thinking, and it will be a good idea to start early. You will be required to use LaTeX to typeset your solutions.
- Project: 40%. You are expected to pick a topic and send a project proposal by October 21. You may work in groups (up to 2 members).
- Participation: 5%.
Resources
The main reference for the course will be scribed lecture notes.
The following are some very useful resources:
- Pseudorandomness by Salil Vadhan. (Excellent book that will serve as a great reference for many of the topics in this course.)
- Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan is a great source for the prerequisite probability theory background for this course.
- Expander graphs by Shlomo Hoory, Nati Linial, and Avi Wigderson.
Here is a link to the Fall'19 edition of this course. Additional resources are listed below.
(will be updated as the semester progresses)
- Lecture 1: Introduction
- Lecture 2: Probabilistic Complexity Classes, error-reduction in algorithms. notes
- Lecture 3: Pairwise Independence notes
- Lecture 4: Derandomizing Max-Cut, k-wise independent distributions. notes
- Lecture 5: Lower bound on randomness requirement for k-wise independent distributions, Pseudorandom Generators. notes
- Lecture 6: Boolean ciruits, existence of good PRGs. notes
- Lecture 7: Small-biased distributions, introduction to error-correcting codes notes
- Lecture 8: Error-corecting codes I: Basics notes
- Lecture 9: Error-correcting codes II: Error-correcting Reed-Solomon Codes notes
- Lecture 10: Error-correcting codes III: Linear codes, Connections to k-wise independence (notes from Fall'18)
- Lecture 11: Balanced Codes and small-biased distributions. Introduction to hardness vs randomness. notes
- Lecture 12: Pseudorandom generator with 1 bit stretch. notes
- Lecture 13: Nisan-Wigderson PRG construction notes
- Lecture 14: Combinatorial Design construction. Introduction to Extractors. notes
- Lecture 15: Randomness Extractors I: Basics notes
- Lecture 16: Randomness Extractors II: Existence of Seeded Extractors notes
- Lecture 17: Randomness Extractors III: Simulating BPP with weak sources, Sampling with a weak source notes
- Lecture 18: Seeded Extractors I: Leftover Hash Lemma notes
- Lecture 19: Seeded Extractors II: Trevisan's Extractor notes
- Lecture 20: Expander Graphs I: vertex expansion, spectral expansion, expander mixing lemma notes (Guest lecturer: Jyun-Jie Liao)
- Lecture 21: Expander Graphs II: random walks on expanders and applications notes (Guest lecturer: Mohit Gurumukhani)
- Lecture 22: Derandomizing space-bounded computation
Inclusiveness
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: