https://blog.computationalcomplexity.org/2025/06/the-new-godel-prize-winner-tastes-great.html Computational Complexity Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch Monday, June 09, 2025 The New Godel Prize Winner Tastes Great and is Less Filling [zuckerman] David Zuckerman The 2025 Godel 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] Eshan Chattopadhyay pseudorandomness! In fact the only interesting thing to come out of Ramsey Theory is the Probabilistic Method (see our discussion of this here). 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 Godel 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. Posted by gasarch at 9:23 AM # # Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest No comments: Post a Comment Older Post Home Subscribe to: Post Comments (Atom) Books [9780691175] Commissions earned from Amazon Links Mastodon Feed Blog Links * Bill's Home Page * Lance's Home Page * Posts Feed * Comments Feed * Favorite Theorems * Foundations of Complexity Lessons * Graduate Student Guide * ChatPNP * Ask Questions to the Blog * CACM P v NP Survey (2009) * CACM Fifty Years of P vs. NP (2022) * CACM Conference Viewpoint * Podcasts * Videos Popular Posts * FOCS Accepts and a Movie * The New Godel Prize Winner Tastes Great and is Less Filling * Intelligent questions about the alleged P NE NP proof * You Need Much Less Memory than Time * The 17x17 challenge. Worth $289.00. This is not a joke. * What was the recent Nobel Prize in Physics really about?(Guest Post) * The Problems of LaTeX * Why did 1+1=2 take Russell and Whitehead 300 pages? * NRC Rankings * Is this problem too hard for a HS Math Competition Complexity Links * Complexity Conference * SIGACT * Theory Announcements * Theory Stack Exchange * Complexity Zoo * Complexity on arXiv * Electronic Colloquium on Computational Complexity Blog Archive * V 2025 (44) + V June (3) o The New Godel Prize Winner Tastes Great and is Les... o Rules vs Standards o Complexity theory of hand-calculations + > May (8) + > April (8) + > March (9) + > February (6) + > January (10) * > 2024 (102) + > December (7) + > November (7) + > October (9) + > September (9) + > August (7) + > July (8) + > June (11) + > May (9) + > April (9) + > March (8) + > February (8) + > January (10) * > 2023 (92) + > December (6) + > November (8) + > October (8) + > September (7) + > August (8) + > July (9) + > June (6) + > May (9) + > April (7) + > March (8) + > February (8) + > January (8) * > 2022 (77) + > December (7) + > November (7) + > October (9) + > September (6) + > August (7) + > July (6) + > June (5) + > May (6) + > April (5) + > March (6) + > February (7) + > January (6) * > 2021 (89) + > December (6) + > November (7) + > October (8) + > September (8) + > August (9) + > July (7) + > June (7) + > May (8) + > April (8) + > March (7) + > February (6) + > January (8) * > 2020 (76) + > December (8) + > November (7) + > October (7) + > September (7) + > August (6) + > July (6) + > June (6) + > May (7) + > April (7) + > March (9) + > February (1) + > January (5) * > 2019 (84) + > December (4) + > November (3) + > October (8) + > September (7) + > August (2) + > July (8) + > June (9) + > May (9) + > April (9) + > March (8) + > February (8) + > January (9) * > 2018 (100) + > December (7) + > November (8) + > October (10) + > September (8) + > August (9) + > July (8) + > June (8) + > May (9) + > April (9) + > March (8) + > February (8) + > January (8) * > 2017 (102) + > December (7) + > November (8) + > October (9) + > September (8) + > August (9) + > July (9) + > June (9) + > May (9) + > April (9) + > March (8) + > February (8) + > January (9) * > 2016 (102) + > December (9) + > November (8) + > October (9) + > September (7) + > August (8) + > July (7) + > June (10) + > May (9) + > April (10) + > March (8) + > February (9) + > January (8) * > 2015 (103) + > December (7) + > November (9) + > October (9) + > September (8) + > August (9) + > July (9) + > June (10) + > May (8) + > April (9) + > March (9) + > February (8) + > January (8) * > 2014 (111) + > December (8) + > November (8) + > October (10) + > September (11) + > August (9) + > July (9) + > June (11) + > May (10) + > April (10) + > March (8) + > February (8) + > January (9) * > 2013 (108) + > December (9) + > November (8) + > October (8) + > September (11) + > August (9) + > July (9) + > June (8) + > May (9) + > April (10) + > March (9) + > February (9) + > January (9) * > 2012 (132) + > December (7) + > November (9) + > October (12) + > September (10) + > August (10) + > July (9) + > June (10) + > May (12) + > April (12) + > March (15) + > February (14) + > January (12) * > 2011 (134) + > December (10) + > November (10) + > October (12) + > September (13) + > August (10) + > July (10) + > June (14) + > May (11) + > April (12) + > March (12) + > February (11) + > January (9) * > 2010 (191) + > December (8) + > November (12) + > October (15) + > September (14) + > August (18) + > July (15) + > June (17) + > May (20) + > April (22) + > March (20) + > February (15) + > January (15) * > 2009 (249) + > December (16) + > November (19) + > October (23) + > September (21) + > August (21) + > July (23) + > June (23) + > May (22) + > April (21) + > March (22) + > February (20) + > January (18) * > 2008 (253) + > December (19) + > November (18) + > October (27) + > September (21) + > August (19) + > July (22) + > June (23) + > May (23) + > April (22) + > March (20) + > February (21) + > January (18) * > 2007 (159) + > December (10) + > November (15) + > October (18) + > September (10) + > August (13) + > July (11) + > June (8) + > May (8) + > April (7) + > March (16) + > February (20) + > January (23) * > 2006 (238) + > December (18) + > November (22) + > October (22) + > September (19) + > August (24) + > July (18) + > June (18) + > May (18) + > April (18) + > March (21) + > February (20) + > January (20) * > 2005 (237) + > December (18) + > November (20) + > October (24) + > September (19) + > August (22) + > July (17) + > June (19) + > May (21) + > April (19) + > March (17) + > February (17) + > January (24) * > 2004 (200) + > December (18) + > November (16) + > October (19) + > September (15) + > August (16) + > July (15) + > June (18) + > May (13) + > April (13) + > March (17) + > February (16) + > January (24) * > 2003 (149) + > December (13) + > November (12) + > October (15) + > September (11) + > August (7) + > July (11) + > June (13) + > May (10) + > April (15) + > March (15) + > February (11) + > January (16) * > 2002 (76) + > December (20) + > November (17) + > October (15) + > September (18) + > August (6) Blog Roll * Thoughts Liable man 9 hours ago * 11011110 Two recent preprints 1 day ago * GovAffairs Department of Energy FY 2026 Request: ASCR Flat Funded While Office of Science Receives Significant Cut 3 days ago * Combinatorics and more Erdos Lectures 2025: Mehtaab S. Sawhney, June 5,9 & 11 4 days ago * What's new Decomposing a factorial into large factors (second version) 5 days ago * Daniel Lemire's blog Fast character classification with z3 1 week ago * Shtetl-Optimized "If Anyone Builds It, Everyone Dies" 1 week ago * Mathematical Enchantments Math and the Museum 2 weeks ago * Process Algebra Diary PhD Position in Probabilistic Session Types at the IT University of Copenhagen 5 weeks ago * Theory Dish Choosing the best ring ... for MPC! 1 month ago * Windows On Theory Call for papers Information-Theoretic Crpytography 2 months ago * Turing's Invisible Hand 2025 Godel Prize: Call for Nominations (Due April 11) 3 months ago * Healthy Algorithms AI for Interview Prep 4 months ago * Godel's Lost Letter and P=NP 5 months ago * Bits and Pieces Bill Ackman's Analysis of Harvard 8 months ago * Theory Matters FOCS 2024 Test of Time Awards Nominations 1 year ago * in theory FOCS Test of Time Awards 1 year ago * The Big Data Theory How I Spent Last Summer FAQ 5 years ago * Opinions of Doron Zeilberger Show 10 Show All Creative Commons License Computational Complexity Weblog by Lance Fortnow and William Gasarch is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Additional permissions can be requested. Powered by Blogger.