Almost Chor--Goldreich Sources and Adversarial Random Walks

by Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman

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:

Indeed, the foregoing question is extremely vague. It is actually a meta-question or a collection of numerous concrete questions. In particular, it refers to possible interpretations of the terms `natural' and `more efficient' (whereas the latter may refer both to notions of computational complexity and to the use of additional randomness (i.e., a seed)).

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:

(These are actually two type of questions: The first refers to the distribution of the end vertex, and the second to the sequence of intermediate vertices. In both cases, the `pseudorandomness' of the walk (choice of steps) is left vague on purpose; the same holds also w.r.t the `pseudorandomness' of the sequence of intermediate vertices in the second type, and the term `quasi-uniform' in the first type.)

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:

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

Available from ECCC TR22-103.

Back to list of Oded's choices.