突破性成果:高效构造 Ramsey 图

Eshan Chattopadhyay 和 David Zuckerman 因其在 2016 年 STOC 和 2019 年 Annals of Math 上发表的论文“显式两源提取器和弹性函数”获得了 2025 年 Gödel 奖。该论文的核心成果是改进了一种构造 Ramsey 图的方法,其构造的 Ramsey 图大小达到了指数级别,远超之前的构造方法。这一突破不仅在去随机化领域具有重要意义,也为 Ramsey 理论提供了新的见解,引发了关于其在伪随机性和 Ramsey 理论中的双重价值的讨论。