2024/10/10 by Jesse Goodman, Xin Li, Goodman, Jesse +3 · 1 citation
Arts and Humanities · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Musicology and Musical Analysis
paper · pdf · doi:10.48550/arxiv.2410.08142
openalex publication_date 2024/10/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
One 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 X=(X1,…,Xt)∼(\0,1\n)t, where each Xi has min-entropy k conditioned on any fixing of X1,…,Xi-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= 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.