Gabizon A. Deterministic Extraction from Weak Random Sources

Springer, 2011. — 161 p.Roughly speaking, a deterministic extractor is a function that ‘extracts’ almost perfect random bits from a ‘weak random source’ - a distribution that contains some entropy but is far from being truly random. In this book we explicitly construct deterministic extractors and related objects for various
types of sources. A basic theme in this book is a methodology of recycling randomness that enables increasing the output length of deterministic extractors to near-optimal length. Our results are as follows.
A question that arises is: How can we be sure that these methods produce truly random bits? By truly random bits we mean that each bit is 1 with probability 1/2 and is independent of all the other bits in the sequence generated. The first method, assuming the validity of quantum mechanics, is theoretically guaranteed to produce truly random bits. The other two methods described, and most methods used, offer no such guarantee. The quality of the numbers produced by these methods is checked empirically by statistical tests but there is no reason to assume that these methods produce truly random bits. To summarize, it seems that while it is possible to get truly random bits from nature, we have an abundance of very cheap and accessible weak random sources and it would be very convenient to be able to use these sources.Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed
Deterministic Extractors for Affine Sources over Large Fields
Extractors and Rank Extractors for Polynomial Sources
Increasing the Output Length of Zero-Error Dispersers