Next: An Improved Parallel Algorithm
Up: The Post-Doctoral Period (1983-86)
Previous: Unbiased Bits From Sources
The question addressed is that of the possibility of extracting
random bits from several bits, where a bounded number of these bits
(incloding the choice of their identity) are
controlled by an adversary and the rest are uniformly distributed.
Lower and upper bounds on the number of uniformly distributed bits
that can be extracted, as a function of the fraction of bits
controlled by the adversary, are presented.
Among the is a lower bound on the size of
sample spaces for limited-independence random variables.
Comments:
Authored by B. Chor, J. Friedmann, O. Goldreich, J. Hastad, S. Rudich
and R. Smolansky. Appeared in
- Proc. of the 26th FOCS, 1985, pp. 396-407.
Oded Goldreich
2003-07-30