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.