Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-054 | 24th April 2025 17:28

Extractors for Samplable Distribution with Polynomially Small Min-Entropy

RSS-Feed




TR25-054
Authors: Ronen Shaltiel
Publication: 24th April 2025 17:28
Downloads: 76
Keywords: 


Abstract:

Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions. They showed that under a very strong complexity theoretic hardness assumption (specifically, that there exists a problem in $\E=\DTIME(2^{O(n)})$ that cannot be computed by size $2^{\Omega(n)}$ circuits that have an oracle to $\Sigma_6^{\P}$) there are extractors for samplable distributions with large min-entropy of $k=(1-\gamma) \cdot n$, for some small constant $\gamma>0$. Recently, Ball, Shaltiel and Silbak (STOC 2025) were able to reduce the min-entropy threshold to $k=n^{1-\gamma}$. Ball et al., point out that their approach does not work for $k\frac{1}{i}$, we construct an extractor for samplable distributions with min-entropy $k=n^{\alpha}$, under a hardness assumption in which $6$ is replaced with $i+3$ (the aforementioned result is a obtained for $i=3$).
We also provide a multiplicative version of our extractors (under a stronger hardness assumption) addressing an open problem of Ball et al.

Our work builds on the approach of Ball et al., who reduced the task of constructing extractors for samplable distributions with min-entropy $k$, to the task of constructing errorless condensers for samplable distributions with min-entropy $k$. Our main technical contribution is a new construction of errorless condensers for samplable distributions with $k=n^{\alpha}$ under the hardness assumption stated above, improving upon the min-entropy threshold achieved in Ball et al. (which cannot achieve $k<\sqrt{n}$).

Our insight is that the technique used by Ball et al. to reduce the task of constructing extractors to that of constructing errorless condensers, can \emph{itself} be used to construct errorless condensers for polynomially small min-entropy when combined with ``win-win analysis'' approaches that are inspired by some early work on seeded extractors and dispersers. In order to do this, we adapt these approaches from the information theoretic scenario of seeded extractors and dispersers to the computational scenario of errorless condensers for samplable distributions.



ISSN 1433-8092 | Imprint