Extracting Randomness from Samplable Distributions

DSpace/Manakin Repository

Extracting Randomness from Samplable Distributions

Citable link to this page


Title: Extracting Randomness from Samplable Distributions
Author: Trevisan, Luca; Vadhan, Salil P.

Note: Order does not necessarily reflect citation order of authors.

Citation: Trevisan, Luca and Salil Vadhan. 2000. Extracting randomness from samplable distributions. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science: November, 12-14, 2000, Redondo Beach, 32-42, Los Alamitos, California: IEEE Computer Society.
Full Text & Related Files:
Abstract: The standard notion of a randomness extractor is a procedure which converts any weak source of randomness into an almost uniform distribution. The conversion necessarily uses a small amount of pure randomness, which can be eliminated by complete enumeration in some, but not all, applications.

Here, we consider the problem of deterministically converting a weak source of randomness into an almost uniform distribution. Previously, deterministic extraction procedures were known only for sources satisfying strong independence requirements. In this paper, we look at sources which are samplable, i.e., can be generated by an efficient sampling algorithm. We seek an efficient deterministic procedure that, given a sample from any samplable distribution of sufficiently large min-entropy, gives an almost uniformly distributed output. We explore the conditions under which such deterministic extractors exist.

We observe that no deterministic extractor exists if the sampler is allowed to use more computational resources than the extractor. On the other hand, if the extractor is allowed (polynomially) more resources than the sampler, we show that deterministic extraction becomes possible. This is true unconditionally in the nonuniform setting (i.e., when the extractor can be computed by a small circuit), and (necessarily) relies on complexity assumptions in the uniform setting.

One of our uniform constructions is as follows: assuming that there are problems in E=DTIME(2^{{O(n)}) that are not solvable by subexponential-size circuits with Sigma_6 gates, there is an efficient extractor that transforms any samplable distribution of length n and min-entropy (1-gamma)n into an output distribution of length (1-O(gamma))n, where gamma is any sufficiently small constant. The running time of the extractor is polynomial in n and the circuit complexity of the sampler. These extractors are based on a connection between deterministic extraction from samplable distributions and hardness against nondeterministic circuits, and on the use of nondeterminism to substantially speed up "list decoding" algorithms for error-correcting codes such as multivariate polynomial codes and Hadamard-like codes.
Published Version: http://dx.doi.org/10.1109/SFCS.2000.892063
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:4728401
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search