Recycling random bits in parallel

Shows that r pseudo-random bits can be obtained by concatenating t blocks of r/t pseudo-random bits, where the blocks are generated in parallel. This can be considered as a parallel version of R. Impagliazzo and D. Zuckerman´s (1989) method of recycling random bits by doing a random walk on an expander. The proof is based on the fact that t simultaneous independent random walks on an expander graph is equivalent to a random walk on a much larger expander. Impagliazzo and Zuckerman´s method of generating the random walk required arithmetic operations with long integers. In the authors´ parallel version, the integers involved are much shorter, and different segments of the pseudo-random bits are generated independently in parallel. Optimal speedup is also achieved