In this course, we will develop provably good pseudorandom generators (PRGs) for a variety of tasks. We will also study several important, related pseudorandom objects: expander graphs, randomness extractors, and error-correcting codes. We will discuss several recent results, including algebraic extractors from codes, applications of additive number theory, pseudorandom generators for polynomials, and SL=L. A tentative list of topics and approximate times follows.

Basics: Introduction, basic coding theory, k-wise independence (1-2 weeks).

Fourier Analysis: small-bias sets, almost k-wise independence, linearity test, PRG for polynomials (1-2 weeks).

Expander Graphs: connection with small-bias sets, Chernoff bound for random walks, explicit constructions, SL=L (2 weeks).

Randomness Extractors: Leftover Hash Lemma, relation to expanders, constructions (2 weeks).

PRGs for Space-Bounded Computation: PRGs from extractors and expanders (1 week).

Polynomial Method and List Decoding: List decoders for RS codes and Parvaresh-Vardy codes, uses for extractors, Kakeya sets and mergers (2 weeks).

Additive Number Theory: Sum-product theorem and incidence theorem, 1-bit condenser, 2-source extractor (1 week).

PRGs and Hardness: cryptographic setting and hardcore bits, derandomization setting, extractors from black-box PRGs (2 weeks).

Citation policy: If you use a solution or part of a solution that you found in the literature or on the web, you must cite it. Furthermore, you must write up the solution in your own words.

Late policy: Each student has five late days that they can use during the semester with no penalty (e.g., one assignment two days late and one three days late). Once late days are used up, no credit will be given for late assignments. A day here means 24 hours (so it begins and ends at 11am). Friday 11am to Monday 11am counts as one day.