Detail

The Many Faces of Randomness Generation

Streams of independent uniformly random bits are a fundamental resource in computer science, from cryptography to machine learning and beyond. But… where do these unbiased random bits come from? Physical sources of randomness introduce correlations between outputs, and so care is needed to “extract” unbiased randomness from them. And, to make matters worse, in many distributed settings we must also ensure that several mutually distrusting parties generate *common* unbiased random bits. In this talk I will give a semi-technical overview of my work on randomness generation, along with some of the subject’s history. This ranges all the way from the theory of randomness extractors, combinatorial objects whose genesis goes back to questions of Erd?s about Ramsey graphs, to more practically-minded challenges related to distributed randomness generation, and to the use of randomness extractors to tackle other seemingly unrelated problems in cryptography. This talk is based on joint work with many people