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 <1990Jun14.144138.23518@jarvis.csri.toronto.edu> 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