next up previous
Next: An Improved Parallel Algorithm Up: The Post-Doctoral Period (1983-86) Previous: Unbiased Bits From Sources

The Bit Extraction Problem or t-Resilient Functions

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



Oded Goldreich
2003-07-30