The Leftover Hash Lemmma states that given a random variable X with min-entropy H∞(X), we can extract a length asymptotic to H∞(X) bits from X that are almost uniformly distributed. This is useful for privacy amplification, where an adversary has partial knowledge of the random variable X.
UC Berkeley
Fall 2021
This course explores the role of randomness in computation and pseudorandomness, focusing on the applications in error-correcting codes, expander graphs, randomness extractors, and pseudo-random generators. The course will also address the question of derandomization of small-space computation. Prerequisites are unspecified, but the course content suggests a high level of expertise.
No concepts data
+ 26 more concepts