Computer Science/Discrete Mathematics Seminar II

Randomness is a vital resource in computation, with many applications in areas such as cryptography, data-structures and algorithm design, sampling, distributed computing, etc. However generating truly random bits is expensive, and most sources in nature produce correlated bits. A randomness extractor is informally defined to be an algorithm that can purify such defective sources of randomness to output purely random bits.

The area of randomness extraction has a long and rich history of studying various models of defective sources, and this line of investigation has uncovered various interesting connections  to mathematics as well as other areas within theoretical computer science.  Recently, this area has seen exciting progress on many longstanding open problems, which have also led to progress on related questions in extremal combinatorics (such as explicit constructions of Ramsey graphs). In this talk, I will survey these results and the new techniques that have led to this progress. I will also discuss open questions that seem within reach.

No prior background in randomness extraction will be assumed for this talk.