Extractors and Ramsey graphs

Mathematical Conversations
Topic:Extractors and Ramsey graphs
Speaker:Eshan Chattopadhyay
Affiliation:Member, School of Mathematics
Date:Friday, October 21
Time/Room:6:00pm - 7:00pm/Dilworth Room

Randomness is widely used in various areas of computer science, and many of the applications require uniform, uncorrelated bits. 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 problem 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). This problem was raised by Chor and Goldreich, and Santha and Vazirani in the 80's. In joint work with David Zuckerman, we resolve this problem. Further, 2-source extractors can be used to construct Ramsey graphs. Using our result, we construct Ramsey graphs within quasi-polynomial factors of the existential bound proved by Erdos in 1947. This is in a line of work spanning the last 67 years in an attempt to meet Erdos' challenge of matching the probabilistic bound. I will introduce the area of randomness extraction, discuss connections to Ramsey graphs and, if time permits, present some ideas of our construction.