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
- Basic introduction to pseudorandomness and derandomization. Will include introduction to simple pseudorandom distributions, hash functions, some properties of polynomials over finite fields, error correcting codes, and expander graphs.
- Producing random bits from defective sources and applications. This topic will be studied in depth. The key notion is 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 in the space-bounded setting: A basic question in computational complexity theory is whether using random bits can save the amount of space used by algorithms. We will study this in detail.
Grading:
- 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 the scribed notes by 48 hours after the lecture.
- Homeworks: 20%. There will be 2 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 28. You may work in groups (up to 2 members).
- Participation: 10%. You are expected to show up to class and participate in discussions.
- Lecture 1: Introduction. pdf
- Lecture 2: Pairwise Independence. pdf
- Leture 3: k-wise independence, Probabilistic method. pdf
- Lecture 4: Expander graphs pdf
- Lecture 5: Expander Mixing Lemma, vertex expansion from spectral expansion pdf
- Lecture 6: Randon walks on Expanders I: Hitting property pdf
- Lecture 7: Random walks on Expanders II: chernoff bound pdf
- Lecture 8: Graph products pdf
- Lecture 9: Zig-zag product and construction of explicit expanders pdf
- Lecture 10: Introduction to randomness extraction
- Lecture 11: Seeded extractors, hash functions pdf
- Lecture 12: Leftover hash lemma, extractors from expanders pdf
- Lecture 13: Introduction to error-correcting codes pdf (lecturer: Jesse Goodman)
- Lecture 14: Gilbert-Varshamov bound pdf
- Lecture 15: Unique decoding Reed-Solomon codes, Johnson bound for list-decoding radius pdf
- Lecture 16: List decoding Reed-Solomon codes, Seeded extractor from codes pdf
- Lecture 17: List view of expanders, graph view of list-decodable codes pdf
- Lecture 18: Lossless vertex expanders from PV codes pdf
- Lecture 19: The Hadamard two-source extractor
- Lecture 20: 2-source extractors from Paley graphs
- Lecture 21: Small-biased spaces: constructions and connections
- Lecture 22: Space bounded derandomization: Nisan's generator pdf
Resources
The main reference for the course will be scribed lecture notes.
A link to the Fall'18 edition of this course.
Other resources: