TY - GEN

T1 - Recycling random bits in parallel

AU - Friedl, K.

AU - Tsai, Shi-Chun

N1 - Publisher Copyright:
© 1995 IEEE.

PY - 1995

Y1 - 1995

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85062626298&partnerID=8YFLogxK

U2 - 10.1109/HICSS.1995.375482

DO - 10.1109/HICSS.1995.375482

M3 - Conference contribution

AN - SCOPUS:85062626298

T3 - Proceedings of the Annual Hawaii International Conference on System Sciences

SP - 14

EP - 19

BT - Proceedings of the 28th Annual Hawaii International Conference on System Sciences, HICSS 1995

PB - IEEE Computer Society

T2 - 28th Annual Hawaii International Conference on System Sciences, HICSS 1995

Y2 - 3 January 1995 through 6 January 1995

ER -