Jürg Wullschleger

Extracting uniform randomness from a long string x of length n using a two-universal hash function or an extractor may be very inefficient. We show that the bounds given in König-Renner also apply to the case where the sample is chosen bitwise uniformly, instead of (recursively) in blocks. We also prove a new min-entropy sampling theorem using a completely different approach. As corollary we obtain a lower bound for random access codes: for any k-out-of-n random access code where the storage is bounded by m <= (1-epsilon)n, the success probability is at most 2^{-Omega(k)}.