ECCC-Report TR24-154https://eccc.weizmann.ac.il/report/2024/154Comments and Revisions published for TR24-154en-usFri, 11 Oct 2024 00:49:41 +0300
Paper TR24-154
| Improved Condensers for Chor-Goldreich Sources |
Jesse Goodman,
Xin Li,
David Zuckerman
https://eccc.weizmann.ac.il/report/2024/154One of the earliest models of weak randomness is the Chor-Goldreich (CG) source. A $(t,n,k)$-CG source is a sequence of random variables $\mathbf{X}=(\mathbf{X}_1,\dots,\mathbf{X}_t) \sim (\{0,1\}^n)^t$, where each $\mathbf{X}_i$ has min-entropy $k$ conditioned on any fixing of $\mathbf{X}_1,\dots,\mathbf{X}_{i-1}$. Chor and Goldreich proved that there is no deterministic way to extract randomness from such a source. Nevertheless, Doron, Moshkovitz, Oh, and Zuckerman showed that there is a deterministic way to condense a CG source into a string with small entropy gap. They gave applications of such a condenser to simulating randomized algorithms with small error and to certain cryptographic tasks. They studied the case where the block length $n$ and entropy rate $k/n$ are both constant.
We study the much more general setting where the block length can be arbitrarily large, and the entropy rate can be arbitrarily small. We construct the first explicit condenser for CG sources in this setting, and it can be instantiated in a number of different ways. When the entropy rate of the CG source is constant, our condenser requires just a constant number of blocks $t$ to produce an output with entropy rate $0.9$, say. In the low entropy regime, using $t=\mathrm{poly}(n)$ blocks, our condenser can achieve output entropy rate $0.9$ even if each block has just $1$ bit of min-entropy. Moreover, these condensers have exponentially small error.
Finally, we provide strong existential and impossibility results. For our existential result, we show that a random function is a seedless condenser (with surprisingly strong parameters) for any small family of sources. As a corollary, we get new existential results for seeded condensers and condensers for CG sources. For our impossibility result, we show the latter result is nearly tight, by giving a simple proof that the output of any condenser for CG sources must inherit the entropy gap of (one block of) its input.Fri, 11 Oct 2024 00:49:41 +0300https://eccc.weizmann.ac.il/report/2024/154