20160520, 01:50  #1 
"Gang aft agley"
Sep 2002
EAA_{16} Posts 
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 offtopic 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 TwoSource 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 20160520 at 01:52 Reason: deleted verbless "sentence" 
20160520, 04:50  #2 
Aug 2006
3×1,993 Posts 
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 lowquality, 'slightlyrandom' 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 20160520 at 05:00 
20160520, 04:56  #3  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×29×83 Posts 
Quote:
But the new paper describes a seedless extractor. No truly uniformly random seed whatever, *only* weak randomness (and lowquality weak at that, not just "slightly weak", for some strict meaning you'd have to go read the blog for). 

20160520, 05:47  #4  
"Gang aft agley"
Sep 2002
2·1,877 Posts 
Quote:
Quote:
From page 2 of the paper: Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
random comments, random questions and thread titles made for Google  jasong  Lounge  46  20170509 12:32 
How to add relations from alternate sources during nfs()  EdH  YAFU  5  20130423 15:55 
About random number (random seed) in Msieve  Greenk12  Factoring  1  20081115 13:56 
Random numbers and proper factors  mfgoode  Math  20  20060205 02:09 
Quality of results  ltd  Prime Sierpinski Project  2  20040810 22:09 