Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-210 | 5th April 2024 05:05

On the Existence of Seedless Condensers: Exploring the Terrain

RSS-Feed




Revision #1
Authors: Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach
Accepted on: 5th April 2024 05:05
Downloads: 16
Keywords: 


Abstract:

While the existence of randomness extractors, both seeded and seedless, has been studied for many sources of randomness, currently, not much is known regarding the existence of seedless condensers in many settings. Here, we prove several new results for seedless condensers in the context of three related classes of sources: Non-Oblivious Symbol Fixing (NOSF) sources, one-sided NOSF (oNOSF) sources (originally defined as SHELA sources in [AORSV, EUROCRYPT'20]), and almost Chor-Goldreich (CG) sources as defined in [DMOZ, STOC'23]. Here, we will think of these sources as a sequence of random variables $\mathbf{X}=\mathbf{X}_1,\dots,\mathbf{X}_\ell$ on $\ell$ symbols where at least $g$ out of these $\ell$ symbols are "good" (i.e., have some min-entropy requirement), denoted as a $(g,\ell)$-source, and the remaining "bad" $\ell-g$ symbols may adversarially depend on these $g$ good blocks. The difference between each of these sources is realized by restrictions on the power of the adversary, with the adversary in NOSF sources having no restrictions.

Prior to our work, the only known seedless condenser upper or lower bound in these settings is due to [DMOZ, STOC'23], where they explicitly construct a seedless condenser for a restricted subset of $(g,\ell)$-adversarial CG sources.

The following are our main results concerning seedless condensers for each of these three sources.
* oNOSF sources
- When $g\leq\ell/2$, we prove that condensing with error 0.99 above rate $\frac{1}{\lfloor \ell/g \rfloor}$ is impossible. In fact, we show that this is tight.
- Quite surprisingly, for $g> \ell/2$, we show the existence of excellent condensers for uniform oNOSF sources. In addition, we show the existence of similar condensers for oNOSF sources with only logarithmic min-entropy. Our results are based on a new type of two-source extractors, called \emph{output-light two-source extractors}, that we introduce and prove the existence of.
* Adversarial CG sources
- We observe that uniform adversarial CG sources are equivalent to uniform oNOSF sources and consequently inherit the same results.
- We show that one cannot condense beyond the min-entropy gap of each block or condense low min-entropy CG sources above rate $1/2$.
* NOSF sources
- We show that condensing with constant error above rate $\frac{g}{\ell}$ is impossible for uniform NOSF sources for any $g$ and $\ell$, thus ruling out the possibility of any non-trivial condensing. This shows an interesting distinction between NOSF sources and oNOSF sources.



Changes to previous version:

Major additions to results and revisions to presentation.


Paper:

TR23-210 | 22nd December 2023 22:26

On the Existence of Seedless Condensers: Exploring the Terrain





TR23-210
Authors: Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach
Publication: 24th December 2023 07:52
Downloads: 138
Keywords: 


Abstract:

While the existence of randomness extractors, both seeded and seedless, has been thoroughly studied for many sources of randomness, currently, very little is known regarding the existence of seedless condensers in many settings. Here, we prove several new results for seedless condensers in the context of three related classes of sources: Non-Oblivious Symbol Fixing (NOSF) sources, SHELA sources as defined by Aggarwal, Obremski, Ribeiro, Siniscalchi, and Visconti [AORSV, EUROCRYPT'20], and almost Chor-Goldreich (CG) sources as defined by Doron, Moshkovitz, Oh, and Zuckerman [DMOZ, STOC'23]. Here, we will think of these sources as a sequence of random variables $\mathbf{X}=\mathbf{X}_1,\dots,\mathbf{X}_\ell$ on $\ell$ symbols where at least $g$ out of these $\ell$ symbols are "good" (i.e., uniformly random), denoted as a $(g,\ell)$-source, and the remaining "bad" $\ell-g$ symbols may adversarially depend on these $g$ good blocks. The difference between each of these sources is realized by restrictions on the power of the adversary, with the adversary in NOSF sources having no restrictions.

Prior to our work, the only known seedless condenser upper or lower bound in these settings is due to [DMOZ, STOC'23] which explicitly constructs a seedless condenser for a restricted subset of $(g,\ell)$-almost CG sources.

The following are our main results concerning seedless condensers for each of these three sources.
1. When $g\leq\ell/2$, we prove for all three classes of sources that condensing with error 0.99 above rate $\frac{1}{\lfloor \ell/g \rfloor}$ is impossible.
2. Next, we investigate the setting of $g> \ell/2$, and in particular focus on $g=2$ and $\ell=3$. We show that condensing with constant error above rate $\frac{2}{3}$ is impossible for uniform NOSF sources.
3. Quite surprisingly, we show the existence of excellent condensers for uniform $(2,3)$-SHELA and uniform almost CG sources, thus proving a separation from NOSF sources. Further, we explicitly construct a condenser that outputs $m = \frac{n}{16}$ bits and condenses any uniform $(2,3)$-SHELA source to entropy $m - O(\log(m / \varepsilon))$ (with error $\varepsilon$). Our construction is based on a new type of seeded extractor that we call output-light, which could be of independent interest.
In contrast, we show that it is impossible to extract from uniform $(2,3)$-SHELA sources.

These results extend seedless extractor lower bounds on NOSF sources (Bourgain, Kahn, Kalai, Katznelson, and Linial [BKKKL, Israel J. Math'92]) and make progress on several open question from [DMOZ, STOC'23], [AORSV, EUROCRYPT'20], and Kopparty and N [KN, RANDOM'23].



ISSN 1433-8092 | Imprint