Almost Chor-Goldreich Sources and Adversarial Random Walks

We typically think of d as constant. We extend this notion in several ways, and most notably allow each X i to be only γ-close to having δd min-entropy. Studying such almost CG sources allows us to achieve pseudorandomness results which were not known to hold even for standard CG sources, and even for the weaker model of Santha-Vazirani sources [SV86]. We construct a deterministic condenser that on input X, outputs a distribution which is close to having constant entropy gap, namely a distribution Z ∼ 0, 1 m for m ≈ δdt with min-entropy m -O(1).

Our new primitive readily implies fast simulation results: