My lecture on Thursday will be on how we can use Expanders to amplify the success of probabilistic algorithms while using an efficient amount of random bits. To start, I'll show how the typical approach of iterating a Monte Carlo algorithm can give an very small probability of failure, but uses n*k bits for some k. The rest of the lecture will be dedicated to show that using a random walk over an expander as our source of randomness keeps the same probability bound, but requires only n+O(k) bits. The following is a rough outline 1. Amplify the success of a probabilistic algorithm 2. Definition of expanders - Adjacency matrix - Eigen vectors and values - Representation by Gabber-Galil 3. Reaching the stationary distribution of an expander 4. Example: Use n+O(k) random bits to achieve small probability of failure The reading will be from the optional textbook "Randomized Algorithms" Section 6.8, which I've attached to this e-mail. Also, one of the readings Yilei gave has some facts on eigen values and vectors which will be useful here as well.