A Chor--Goldreich (CG) source [CG88] is a sequence of random variables $X = X_1 \circ \ldots \circ X_t$, each $X_i \sim \{0,1 \{^d$, such that each $X_i$ has $\delta d$ min-entropy for some constant $\delta > 0$, even conditioned on any fixing of $X_1 \circ \ldots \circ X_{i-1}$. We typically think of $d$ as constant. We extend this notion in several ways, and most notably allow each $X_i$ to be only $\gamma$-close to having $\delta 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 \sim \{0,1 \}^m$ for $m \approx \delta dt$ with min-entropy $m-O(1)$.

Our new primitive readily implies fast simulation results:

* We can simulate $\mathbf{BPP}$ using almost CG sources with constant multiplicative slowdown.
* When the randomized algorithm has small failure probability, we can simulate it using almost CG sources with no multiplicative slowdown. This result extends to randomized protocols as well, and any setting in which we cannot simply cycle over all seeds, and a ``one-shot'' simulation is needed.

Moreover, our framework is flexible enough to work even when the $X_i$-s only have Shannon entropy rather than min-entropy, and in some cases, even when a few $X_i$-s are completely damaged.

Our main technical contribution is a novel analysis of random walks which may be of independent interest. We analyze walks with adversarially correlated steps, each step being entropy-deficient, on good enough lossless expanders. We prove that such walks (or certain interleaved walks on two expanders), starting from a fixed vertex and walking according to $X_1\circ \ldots \circ X_t$, accumulate most of the entropy in $X$.

A Chor--Goldreich (CG) source [CG88] is a sequence of random variables $X = X_1 \circ \ldots \circ X_t$, each $X_i \sim \{0,1 \{^d$, such that each $X_i$ has $\delta d$ min-entropy for some constant $\delta > 0$, even conditioned on any fixing of $X_1 \circ \ldots \circ X_{i-1}$. We typically think of $d$ as constant. We extend this notion in several ways, and most notably allow each $X_i$ to be only $\gamma$-close to having $\delta 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 \sim \{0,1 \}^m$ for $m \approx \delta dt$ with min-entropy $m-O(1)$.

Our new primitive readily implies fast simulation results:

* We can simulate $\mathbf{BPP}$ using almost CG sources with constant multiplicative slowdown.
* When the randomized algorithm has small failure probability, we can simulate it using almost CG sources with no multiplicative slowdown. This result extends to randomized protocols as well, and any setting in which we cannot simply cycle over all seeds, and a ``one-shot'' simulation is needed.

Moreover, our framework is flexible enough to work even when the $X_i$-s only have Shannon entropy rather than min-entropy, and in some cases, even when a few $X_i$-s are completely damaged.

Our main technical contribution is a novel analysis of random walks which may be of independent interest. We analyze walks with adversarially correlated steps, each step being entropy-deficient, on good enough lossless expanders. We prove that such walks (or certain interleaved walks on two expanders), starting from a fixed vertex and walking according to $X_1\circ \ldots \circ X_t$, accumulate most of the entropy in $X$.

A Chor--Goldreich (CG) source [CG88] is a sequence of random variables $X = X_1 \circ \ldots \circ X_t$, each $X_i \sim \{0,1 \{^d$, such that each $X_i$ has $\delta d$ min-entropy for some constant $\delta > 0$, even conditioned on any fixing of $X_1 \circ \ldots \circ X_{i-1}$. We typically think of $d$ as constant. We extend this notion in several ways, and most notably allow each $X_i$ to be only $\gamma$-close to having $\delta 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 \sim \{0,1 \}^m$ for $m \approx \delta dt$ with min-entropy $m-O(1)$.

Our new primitive readily implies fast simulation results:

* We can simulate $\mathbf{BPP}$ using almost CG sources with constant multiplicative slowdown.
* When the randomized algorithm has small failure probability, we can simulate it using almost CG sources with no multiplicative slowdown. This result extends to randomized protocols as well, and any setting in which we cannot simply cycle over all seeds, and a ``one-shot'' simulation is needed.

Moreover, our framework is flexible enough to work even when the $X_i$-s only have Shannon entropy rather than min-entropy, and in some cases, even when a few $X_i$-s are completely damaged.

Our main technical contribution is a novel analysis of random walks which may be of independent interest. We analyze walks with adversarially correlated steps, each step being entropy-deficient, on good enough lossless expanders. We prove that such walks (or certain interleaved walks on two expanders), starting from a fixed vertex and walking according to $X_1\circ \ldots \circ X_t$, accumulate most of the entropy in $X$.