Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs I

Computer Science/Discrete Mathematics Seminar I
Topic:Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs I
Speaker:Gil Cohen
Affiliation:California Institute of Technology
Date:Monday, November 2
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/2015/1102-GilCohen

In his 1947 paper that inaugurated the probabilistic method, Erdős proved the existence of $2 \log(n)$-Ramsey graphs on $n$ vertices. Matching Erdős' result with a constructive proof is a central problem in combinatorics that has gained a significant attention in the literature. In this talk we will present a recent work towards this goal (http://eccc.hpi-web.de/report/2015/095/).