CSAIL Event Calendar: Previous Series
Speaker: Yuval Ishai , Technion and UCLA
Relevant URL: http://theory.csail.mit.edu/theory-seminars/2009/Spring/yuval.html
Randomness extractors convert dirty sources of randomness into clean sources of randomness. We consider an extension of randomness extraction and the related notion of privacy amplification to the case of two correlated sources. Our main result is an efficient interactive two-party protocol which extracts m clean independent instances of a given joint distribution (X,Y) from n=O(m) dirty (or "leaky") instances of the same distribution. The classical case corresponds to X and Y being identical random bits.