Subject: Re: What the hell did Santha-Vazirani paper actually say?
From: bennyp@techunix.BITNET (Benny Pinkas @ Technion, Israel Inst. Tech., Haifa Israel)
In article <> David Lewis writes:
>The solution I ultimately devised is completely general and efficient.
>It takes a source of bits with some randomness which can be modelled
>by pone(prevbits), giving the probability of seeing a one as the next bit
>given any number of previous bits. The pone function can be arbitrarily
>complicated; as long as it exactly models the non-randomness in the
>input, the output will be completely random. In practice, a table listing
>pone(prevbits) for some finite number of previous bits is sufficient.


I don't have any practical experience, I only deal with theory aspects.
I think that Lewis' work is generalized by M. Blum:
"Independent unbiased coin flips from a correlated biased source: a finite
state Markov chain", combinatorica, 6 (1986), pp. 97-108.
In this work, a source is modelled as a finite state Markov chain (with
unknown transition probabilities). In this mode it is possible to describe the
dependency of the next bit (output by the source), on the previous c bits (for
any constant c).
Santha and Vazirani have further relaxed the restrictions on the physical
source: an output bit may depend on all the preceding bits.
A even weaker model of randomness was suggested by Benny Chor and Oded
Goldreich, and they show for it the same results SV had for their model.

For a good survey, you can look at the introduction to Chor and Goldreich's
paper: "Unbiased bits from  sources of weak randomness and probabilistic
communication complexity", SIAM J. COMPUT., Vol. 17, No. 2, April 1988.

Benny Pinkas