Randomness extractors - applications and constructions

Randomness extractors - applications and constructions

-
Avi Wigderson, IAS
Fine Hall 224

We will investigate the minimal requirements from a random source under which it is potentially useful for generating perfect randomness. The efficient procedures which utilize such sources, "randomness extractors", turn out to have amazing pseudorandomness properties and are useful in numerous contexts. We'll demonstrate applications in complexity theory, error correction and network design. We'll also describe some constructions of near optimal extractors, with tools from expander graphs and the recent proof of the Kakeya conjecture in finite fields.