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
- Basic topics: k-wise independence, basic coding theory, epsilon-bias spaces, hash functions
- Expander graphs: random walks, zig-zag product, SL=L
- Pseudorandom generators for derandomization: Nisan-Wigderson construction, Impagliazzo-Wigderson worst-case to average case reduction.
- Some unconditional derandomization: small depth-circuits, low degree polynomials, space-bounded computation
- Randomness Extractors: seeded and seedless extraction, connections to expanders, explicit constructions
- List-decoding: basics, explicit constructions of seeded extractors from list-decodable codes
- Non-malleable extractors: basics, introduction to privacy amplification, constructions
- Alternating extraction: basics, the flip-flop primitive, correlation breakers
- Extractors for independents sources, Ramsey graphs: constructions based on additive combinatorics, and newer ideas
- Lecture 1: Introductory lecture.
- Lecture 2: Pairwise independence, Pseudorandom generator definition. pdf
- Lecture 3: k-wise independence, small-biased distribution. pdf
- Lecture 4: Small-biased distribution, introduction to Fourier analysis on Abelian groups. pdf
- Lecture 5: Almost k-wise independence, Vazirani's XOR lemma pdf
- Lectures 6,7: The cap-set problem. Fourier analytic approach and new advances based on the polynomial method. (guest lectures by Bobby Kleinberg). pdf
- Lecture 8: Coding theory connections, introduction to polynomial codes. pdf
- Lecture 9: Unique decoding and list-decoding of Reed-Solomon codes, the Johnson bound.
- Lecture 10: Expander graphs, various notions of expansion pdf
- Lecture 11: Expanders continued, random walks on expanders, introduction to Extractors pdf
- Lecture 12: Seeded extractors, Leftover hash lemma pdf
- Lecture 13: More on seeded extractors, Samplers from extractors, a-expanding graphs pdf
- Lecture 14: a-expanding graphs from seeded extractors, Lossless condensers pdf
- Lecture 15, 16: Seeded extractors, lossless condensers, and optimal vertex expanders from list-decodable codes pdf pdf
- Lecture 17: Derandomizing space-bounded computation 1: basics pdf
- Lecture 18: Derandomizing space-bounded computation 2: Nisan type PRG, Nisan-Zuckerman PRG pdf
- Lecture 19: Parameters of Nisan-Zuckerman PRG, 2-source extractors: explicit construction based on the inner product function and Paley graphs pdf
- Lecture 20: Hardness vs Randomness paradigm 1: warm-up for Nisan-Wigderson PRG pdf
- Lecture 21: Hardness vs Randomness paradiigm 2: Nisan-Wigderson PRG pdf
- Lecture 22: Seeded extractors from Nisan-Wigderson style argument: Trevisan's Extractor. Explicit affine extractors based on the inner product function.
- Lecture 23: Explicit spectral expanders via the Zig-Zag product pdf
- Lecture 24: Constant-degree lossless vertex expanders pdf
Resources
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
- Cayley expanders and the zig-zag product. Tjaden Hess, Linus Setiabrata, Cosmo Viola. pdf
- Pseudorandom generators from the Fourier spectrum. Jason Gaitonde. pdf
- Concentration of measure in the matrix-valued dependent setting. Juan C. Martinez Mori, Ayush Sekhari. pdf
- Easy witness and hard circuit lower bounds. Shawn Ong. pdf
- Towards derandomizing RL via graph connectivity. Jyun-Jie Liao and Wei-Kai Lin. pdf