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

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

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

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

DateTopicsReadingsAssignmentsNotesPolynomial Identity Testing,

Schwartz-Zippel Lemma, and

applications; Randomized Min-cut

Chapter 1 of PC

Anthi Orfanou

Random variables and expectation;

Coupon collector's problem; Markov's

inequality and Jensen's inequality;

and 1-level Hashing

Section 10.2 of RA

Chapter 2 of PC

David Solimano

and Standard deviation; Chebyshev

inequality; Coupon collector revisited;

Two-point sampling; and a randomized

algorithm for computing the median

Chapter 3 of PC

Chapter 3 of RA

ClĂ©ment Canonne

Randomized rounding, Chernoff bound

and applications: Set balancing and

Minimizing Hamming distance

Chapter 4 of PC

Chun Ye

and applications: Pattern matching, balls

and bins, chromatic number, and traveling

sales man in a hypercube.

Chapter 12 of PC

Set-balancing revisited; Derandomization

using conditional expectations; Existence

of an approximate Nash equilibrium with

small support

Section 6.1 -- 6.4 of PC

Playing large games using simple strategies

by Lipton, Markakis, and

David Solimano

Lovasz Local Lemma

Section 6.4 -- 6.9 of PC

time and effective resistance; Expander

graphs; Split(G) and the second largest

eigenvalue; Rapid mixing of random walks

on an expander graph

Michael Rubin

Counting the number of independent sets;

From sampling to approximate counting

Raanan Cohen

The coupling lemma; Coupling for bounding

the mixing time of Markov chains

Section 6.2 of RA

walks on the hypercube; Approximate

sampling a proper coloring

Geometric Convergence; Path coupling;

Approximate sampling a coloring revisited

RA: Randomized Algorithms, PC: Probability and Computing