Mutual Information and Randomness Extraction

Intro

Several works have shown that, if we have many independent sources, each having enough 'randomness', then we can extract pure randomness from them. Anup Rao recently showed that another assumption also suffices for randomness extraction, i.e. the source is generated by small space Turing machine.

One is tempted to ask the question whether another weaker assumption implies the possibility of randomness extraction, so basically we are looking at this problem where the assumption of interest is the notion of 'almost' independent sources.

An interesting special case to study is one that we are given two independent sources. In this case, the best known extractor was given by Bourgain.