Computer Sciences Colloquium - Recent advances in randomness extractors and their applications

Abstract:

We present recent developments in randomness extractors theory and applications to classical, long-standing, open problems such as Ramsey graphs constructions and privacy amplification protocols. This exciting progress heavily relies on two new pseudo-random primitives we call correlation breakers and independence-preserving mergers, which we discuss.

Short bio:

Gil Cohen is a postdoctoral researcher at Princeton University working with Mark Braverman. He obtained his Ph.D. in 2015 from The Weizmann Institute of Science under the guidance of Ran Raz. In 2015-16 he was a postdoctoral fellow at Caltech, hosted by Leonard Schulman and Thomas Vidick. His interests lie mostly in theoretical computer science with a focus on computational complexity, pseudo-randomness, and explicit constructions.