mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2016-05-20, 01:50   #1
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

3,581 Posts
Default Combining low quality random numbers sources

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

Last fiddled with by only_human on 2016-05-20 at 01:52 Reason: deleted verbless "sentence"
only_human is offline   Reply With Quote
Old 2016-05-20, 04:50   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

173216 Posts
Default

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.

Last fiddled with by CRGreathouse on 2016-05-20 at 05:00
CRGreathouse is online now   Reply With Quote
Old 2016-05-20, 04:56   #3
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·2,399 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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).
Dubslow is offline   Reply With Quote
Old 2016-05-20, 05:47   #4
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

3,581 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
Quote:
Originally Posted by Dubslow View Post
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:
Quote:
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.
only_human is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
random comments, random questions and thread titles made for Google jasong Lounge 46 2017-05-09 12:32
How to add relations from alternate sources during nfs() EdH YAFU 5 2013-04-23 15:55
About random number (random seed) in Msieve Greenk12 Factoring 1 2008-11-15 13:56
Random numbers and proper factors mfgoode Math 20 2006-02-05 02:09
Quality of results ltd Prime Sierpinski Project 2 2004-08-10 22:09

All times are UTC. The time now is 20:29.

Tue Nov 24 20:29:03 UTC 2020 up 75 days, 17:40, 4 users, load averages: 2.53, 2.57, 2.44

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.