 |
| David Zuckerman |
The 2025 Gödel Prize has been awarded to Eshan Chattopadhyay and David Zuckerman for their paper
Explicit two-source extractors and resilient functions
which was in STOC 2016 and in the Annals of Math in 2019.
We (Bill and Lance) care about this result for two different reasons.
BILL: The result has applications to constructive Ramsey---
LANCE: Ramsey Theory? Really? This is a great result about
 |
| Eshan Chattopadhyay |
BILL: Can't it be BOTH a great result in derandomization AND have an application to Ramsey Theory. Like Miller Lite: Less Filling AND Tastes Great (see here)
LANCE: But you don't drink!
BILL: Which means I can give a sober description of their application to Ramsey Theory.
All statements are asymptotic.
Let \(R(k)\) be the least \(n\) so that for all 2-colorings of \(K_n\) there is a homog set of size \(k\).
Known and easy: \(R(k)\le 2^{2k}/\sqrt{k} \)
Known and hard: \(R(k) \le 3.993^k \). How do I know this is true? Either I believe the survey papers on these kinds of results (see here) or a former student of mine emailed me a picture of a T-shirt that has the result (see here) from (of course) Hungary.
Known and Easy and Non-Constructive: \(R(k)\ge k2^{k/2}\)
Can we get a constructive proof? There were some over the years; however, the paper by Eshan Chattopadhyay and David Zuckerman improves the constructive bound to exponential in \( 2^{(\log k)^\epsilon}.\)
SO Lance, why do you care?
LANCE: First of all when I chose this paper as one of my favorite theorems (a far bigger honor than the so-called Gödel Prize) I gave the post the clever title Extracting Ramsey Graphs that captures both the pseudorandomness and the Ramsey graphs. But of course the Ramsey result is just a minor corollary, the ability to get a near perfect random bit out of two independent sources of low min-entropy is the true beauty of this paper.
BILL: You have no sense of good taste.
LANCE: Well at least I'm not less filling.
No comments:
Post a Comment