Combining low quality random numbers sources

[only_human]

An article about a math paper showed up in my news stream:
Academics Make Theoretical Breakthrough in Random Number Generation

It showed up in my news stream because I have previously chosen keywords mathematics and breakthrough which usually aren't particularly good criteria for selecting quality articles.

This article is about combining low quality random number sources to generate higher quality random numbers. I haven't gone back to check but my recollection is that Knuth once fruitlessly tried a naive approach at doing this.

I placed it in Miscellaneous Math because it is a little bit off-topic to the math generally discussed here and also because I am merely pointing at something possibly interesting rather than adding to the conversation.

The paper is:
Explicit Two-Source Extractors and Resilient Functions

by
Eshan Chattopadhyay, Department of Computer Science, University of Texas at Austin
and
David Zuckerman, Department of Computer Science, University of Texas at Austin

Here is a blog post from last year on this paper:
Purifying spoiled randomness with spoiled randomness

[CRGreathouse]

The news article doesn't match my intuition at all. Randomness extractors have been known for a long time -- the usual setup, IIRC, is that they take a (very) short truly uniformly random seed and a low-quality, 'slightly-random' source, and that they could already extract close to the theoretical limit. Maybe this new paper does this more efficiently, either extracting slightly more randomness or with less effort, but I don't think it's the breakthrough advertised unless I'm missing something.

Edit: OK, it looks like I was: this really does allow sources with much less entropy/bit.

[Dubslow]

Originally Posted by CRGreathouse

the usual setup, IIRC, is that they take a (very) short truly uniformly random seed and a low-quality, 'slightly-random' source, and that they could already extract close to the theoretical limit.

The blog linked at the end of his post specifically mentions that such seeded extractors as you describe have been known for a while.

But the new paper describes a seedless extractor. No truly uniformly random seed whatever, *only* weak randomness (and low-quality weak at that, not just "slightly weak", for some strict meaning you'd have to go read the blog for).

[only_human]

Originally Posted by CRGreathouse

The news article doesn't match my intuition at all. Randomness extractors have been known for a long time -- the usual setup, IIRC, is that they take a (very) short truly uniformly random seed and a low-quality, 'slightly-random' source, and that they could already extract close to the theoretical limit. Maybe this new paper does this more efficiently, either extracting slightly more randomness or with less effort, but I don't think it's the breakthrough advertised unless I'm missing something.

Edit: OK, it looks like I was: this really does allow sources with much less entropy/bit.

Originally Posted by Dubslow

The blog linked at the end of his post specifically mentions that such seeded extractors as you describe have been known for a while.

But the new paper describes a seedless extractor. No truly uniformly random seed whatever, *only* weak randomness (and low-quality weak at that, not just "slightly weak", for some strict meaning you'd have to go read the blog for).

Dubslow's post helped clarify my understanding.

From page 2 of the paper:

The lack of progress on constructing two-source extractors motivated researchers to use more than two sources. Several researchers managed to construct excellent extractors using a constant number of sources [BIW06,Rao09a,RZ08,Li11,Li13a,Li13b] culminating in Li's construction of a 3 source extractor for polylogarithmic min-entropy [Li15c]. Recently Cohen [Coh15] also constructed a 3-source extractor with one source having min-entropy n, the second source having min-entropy O(log n) and the third source having min-entropy O(log log n).

Another direction has been the construction of seeded extractors [NZ96]. A seeded extractor uses one (n;k)-source and one short seed to extract randomness. There was a lot of inspiring work over two decades culminating in almost optimal seeded extractors [LRVW03, GUV09, DKSS09]. Such seeded extractors have found numerous applications; see e.g., Shaltiel's survey [Sha02].

However despite much attention and progress over the last 30 years, it remained open to explicitly construct two-source extractors for min-entropy rate signicantly smaller than 1/2.

Our main result is an explicit two-source extractor for polylogarithmic min-entropy.