Title: On parallel randomness extraction procedures
Abstract: In crytography we want to have uniformly (pseudo)random bits, but are sometimes given only nonuniform distributions that have a certain amount of (pseudo)entropy. A popular way to extract the entropy is by applying a pairwise independent hash function. However such functions, while optimal in many other ways, are inherently somewhat sequential.

We investigate the possibility of parallel extraction procedures, where our measure of parallelism is the number of input-output dependencies. We show that for every distribution of min-entropy k on n bits there exists an extractor with O(n log k log(n/k)) dependencies that squeezes out almost all the entropy, and this is optimal up to a constant factor when n^0.99 < k < n/2. We also show that if a uniformly random seed is available, the number of dependencies can be improved.

Based on joint work with SiyaoGuo.