Simulating independence

Abstract

A distribution X over binary strings of length n has min-entropy k if every string has probability at most 2-k in X. We say that X is a δ-source if its rate k⁄n is at least δ.We give the following new explicit instructions (namely, poly(n)- time computable functions) of deterministicextractors, dispersers and related objects. All work for any fixed rate δ>0. No previous explicit construction was known for either of these, for any δ‹1⁄2. The first two constitute major progress to very long-standing open problems.