Almost Chor--Goldreich Sources and Adversarial Random Walks

Oded's comments

This paper addresses a couple of questions that have been on my mind for decades (mostly implicitly and vaguely). The first question is:

For natural models of sources of defective randomness, present extractors that are more efficient, in some senses, than those available for general sources of min-entropy

For sure, Theorems 1 and 2 in this paper answer concrete interpretations of the vague question. In particular, I refer to the constant-length seed in Thm 1 and the seedless condenser of constant deficiency in Thm 2, let alone its construction that is visible in Thm 4.11. This construction refers to a second type of questions that were on my mind for decades:

What type of pseudorandom walks on expander graphs generate quasi-uniform distribution on the end vertex or a pseudorandom sequence of intermediate vertices.

Thm 4.11 addresses the first type of questions. It asserts that choosing the steps according to a CG-source yields a distribution of constant deficiency (after taking a number of steps that have approximately as much randomness as needed in the case of a truly random walk).

(An alternative construction may take a constant number of steps on each graph before moving to a graph that is a constant times larger. That is, we reach constant deficiency on the current graph, embed the vertices of the current graph in part of a larger graph, and take a few additional steps to reach the same deficiency on the larger graph.)

Warning: I find the discussion of Thm 1.2 quite misleading. I was not aware of this result and wonder how many researchers were aware of it, let alone my principled objection to folklore in science. In any case, the proof sketch in FN6 contains a crucial typo; extraction should start at the suffix rather than in the prefix. The analysis itself uses Lemma 6.27 in Salil's lecture notes on Randomness Extractors, while setting $m_2=d_1$; that is, $EXT'((x_1,x_2),y_2))=EXT_1(x_1,EXT_2(x_2,y_2))$).

Acknowledgements: I am grateful to Dean for answering my questions regarding this paper. The foregoing alternative construction was the answer to one of my questions.

The original abstract

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 \geq 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.

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$.

Available from ECCC TR22-103.