Date

Topics

Readings

Assignments

Notes

Sep 10
Introduction; Class overview;
Polynomial Identity Testing,
Schwartz-Zippel Lemma, and
applications; Randomized Min-cut
Chapter 1 of RA
Chapter 1 of PC
Set 1
Note 1 by
Anthi Orfanou


Sep 17
Faster Randomized Min-Cut;
Random variables and expectation;
Coupon collector's problem; Markov's
inequality and Jensen's inequality;
and 1-level Hashing
Section 8.4, 8.5 of RA
Section 10.2 of RA
Chapter 2 of PC

Note 2 by
David Solimano

Sep 24
Perfect Hashing; Moments, Variance
and Standard deviation; Chebyshev
inequality; Coupon collector revisited;
Two-point sampling; and a randomized
algorithm for computing the median
Section 13.3 of PC
Chapter 3 of PC
Chapter 3 of RA
Set 2
Note 3 by
Clément Canonne



Oct 8
Set Cover: LP relaxation and
Randomized rounding, Chernoff bound
and applications: Set balancing and
Minimizing Hamming distance
Section 4.1 -- 4.3 of RA
Chapter 4 of PC
Set 3
Note 4 by
Chun Ye



Oct 15
Martingales; Azuma-Hoeffding bound
and applications: Pattern matching, balls
and bins, chromatic number, and traveling
sales man in a hypercube.
Section 4.4 of RA
Chapter 12 of PC


Oct 22
The probabilistic method; Max cut;
Set-balancing revisited; Derandomization
using conditional expectations; Existence
of an approximate Nash equilibrium with
small support
Section 5.1 -- 5.2, 5.6 of RA
Section 6.1 -- 6.4 of PC
Playing large games using simple strategies
by Lipton, Markakis, and

Note 6 by
David Solimano


Nov 12
Sample and modify
Lovasz Local Lemma
Section 5.5 of RA
Section 6.4 -- 6.9 of PC


Nov 14
Random walks on graphs; Commute
time and effective resistance; Expander
graphs; Split(G) and the second largest
eigenvalue; Rapid mixing of random walks
on an expander graph
Section 6.1 -- 6.7 of RA
Set 4
Note 8 by
Michael Rubin


Nov 19
The Monte Carlo method; DNF counting;
Counting the number of independent sets;
From sampling to approximate counting
Chapter 10 of PC

Note 9 by
Raanan Cohen

Nov 26
Fundamental theorem of Markov chains;
The coupling lemma; Coupling for bounding
the mixing time of Markov chains
Chapter 7 of PC
Section 6.2 of RA

Note 10 byJun Jiang

Nov 27
Mixing time of card shuffling and random
walks on the hypercube; Approximate
sampling a proper coloring
Section 11.2 and 11.5 of PC


Dec 3
Variation distance is nondecreasing;
Geometric Convergence; Path coupling;
Approximate sampling a coloring revisited
Section 11.3 -- Section 11.6 of PC


Dec 10
Approximating the Permant
Section 11.3 of RA



RA: Randomized Algorithms, PC: Probability and Computing