Center for Applied Mathematics Colloquium

Eshan ChattopadhyayCornell University
Explicit Constructions of Ramsey Graphs and Randomness Extractors

Friday, August 31, 2018 - 3:30pm
Rhodes 655

Abstract:
Randomness is widely used in various areas of computer science, and many of the applications require uniform, uncorrelated bit. However, most sources of randomness in nature are defective and at best, only contain some amount of entropy. This leads to the area of randomness extraction, where an extractor is a deterministic procedure to produce pure random bits from a weak source. A central open problem (from the 80s) in this area is to extract from 2 independent weak sources (it is known that it is impossible to extract from just 1 weak source). In joint work with David Zuckerman, we resolve this problem. I will discuss ideas that we use to solve this problem.

As a corollary of our 2-source extractor, we obtain exponential improvements in explicit constructions of Ramsey graphs, a central object in extremal combinatorics. This is in a line of work spanning the last 70 years in an attempt to meet Erdos' challenge of matching the probabilistic method.

Bio:
Eshan Chattopadhyay is an Assistant Professor in the Computer Science Department at Cornell University. He received an B.Tech. in Computer Science from Indian Institute of Technology Kanpur in 2011 and a Ph.D. in Computer Science from UT Austin in 2016. He was a postdoctoral fellow at the Institute for Advanced Study, Princeton from 2016-2018, and at a Microsoft Research Fellow at the Simons Institute for the Theory of Computing in the Spring of 2017.

His research focuses primarily on pseudorandomness and the role of randomness in computing. He is best known for his work on randomness extractors and their applications. His other research interests include complexity theory, coding theory, and cryptography. His research awards include a Best Paper Award at STOC 2016, and the Bert Kay Dissertation Award 2016.