Almost Chor-Goldreich Sources and Adversarial Random Walks
Almost Chor-Goldreich Sources and Adversarial Random Walks
复制标题
DOI：
10.1145/3564246.3585134
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Dean Doron;Dana Moshkovitz;Justin Oh;David Zuckerman
中科院分区：
文献类型：
--
作者：
Dean Doron;Dana Moshkovitz;Justin Oh;David Zuckerman
一个乔格-戈德赖希（CG）源是一个随机变量序列X = X1 <$...<$Xt，其中每个Xi <${0，1}d和Xi都有δ d最小熵，条件是X1 <$...<$Xi−1的任何固定。参数0<δ≤ 1是源的熵率。我们通常认为d是常数，t是增长的。我们扩展这个概念在几个方面，定义几乎CG源。最值得注意的是，我们允许每个Xi只有条件香农熵δ d。我们实现了几乎CG源的伪随机性结果，这些结果甚至对于标准CG源也不成立，甚至对于Santha-Vazirani源的较弱模型也不成立：我们构建了一个确定性电容器，在输入X上输出一个接近于具有恒定熵间隙的分布，即分布Z <${0，1}m，其中m <$δ dt具有最小熵m−O（1）。因此，我们可以模拟任何随机算法与小故障概率几乎CG源没有乘法减速。这个结果也扩展到随机协议，以及任何我们不能简单地在所有种子上循环的设置，并且需要“一次性”模拟。此外，我们的构造以在线方式工作，因为它是基于扩展器上的随机行走。我们的主要技术贡献是随机游走的新分析，这应该是独立的利益。我们分析步行与adversarially相关的步骤，每一步都是熵不足，足够好的无损扩展。我们证明了这样的行走（或某些交错行走在两个扩展），从一个固定的顶点和行走根据X1 <$...<$Xt，积累大部分的熵在X。
A Chor–Goldreich (CG) source is a sequence of random variables X = X1 ∘ … ∘ Xt, where each Xi ∼ {0,1}d and Xi has δ d min-entropy conditioned on any fixing of X1 ∘ … ∘ Xi−1. The parameter 0<δ≤ 1 is the entropy rate of the source. We typically think of d as constant and t as growing. We extend this notion in several ways, defining almost CG sources. Most notably, we allow each Xi to only have conditional Shannon entropy δ d. We achieve pseudorandomness results for almost CG sources which were not known to hold even for standard CG sources, and even for the weaker model of Santha–Vazirani sources: 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). Therefore, we can simulate any randomized algorithm with small failure probability 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 construction works in an online manner, since it is based on random walks on expanders. Our main technical contribution is a novel analysis of random walks, which should 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 X1∘ … ∘ Xt, accumulate most of the entropy in X.