Randomness extractors are functions that take a short, uniformly random seed and output highly random data from a weakly random entropy source. Extractors have similarities to pseudorandom generators, but the output of an extractor must be statistically close to uniform while a PRG only needs to be computationally indistinguishable from uniform. NIST Special Publication 800-90B recommends several extractors for use.
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