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
05/04/2023 14:00
Software Systems
João Ribeiro is an Assistant Professor in the Department of Computer Science of NOVA School of Science and Technology and a researcher at NOVA LINCS. Previously, he was a Post Doctoral Fellow in the Computer Science Department of Carnegie Mellon University hosted jointly by Vipul Goyal and Venkatesan Guruswami. João received his PhD from the Department of Computing of Imperial College London, where he was advised by Mahdi Cheraghchi. Before that, he received an MSc in Computer Science from ETH Zurich and a BSc in Applied Mathematics and Computation from Instituto Superior Técnico. He has broad interests within theoretical computer science, with special emphasis on pseudorandomness, coding theory, and cryptography (plus the connections between these areas). More details can be found at https://sites.google.com/site/joaorib94/.
