2025年，计算机科学界迎来了备受期待的Gödel奖颁布盛典。本年度的殊荣授予了两位杰出的研究者——伊山·查托帕德海（Eshan Chattopadhyay）和大卫·祖克曼（David Zuckerman），以表彰他们在随机性提取领域中的卓越贡献，尤其是在两源提取器构造问题上的突破。他们2016年在STOC会议及之后2019年发表于《数学年刊》（Annals of Mathematics）的一篇开创性论文，彻底解决了困扰计算理论近三十年的核心难题。 随机性在计算机科学中具有极其重要的地位。许多算法和协议依赖于真正的随机数才能确保其安全性和有效性。然而，现实世界中来源的随机数据往往带有偏倚和依赖性，无法保证完全的均匀和独立性。
这种“非完美随机性”严重制约了随机算法的性能和应用范围。随机性提取器的目标正是从这些具有一定随机性的源中提取出接近纯粹均匀的随机比特，广泛应用于密码学、算法设计及复杂性理论。 两源提取器是随机性提取器中一种重要而困难的模型。它假设有两个独立但质量较差的随机源，通过某种方式将它们“合并”，输出高质量的随机比特。尽管看似简单，却是理论计算机科学中的重大难题。此前的研究多依赖于较强的假设或者需要大量的随机位数，无法满足效率与通用性兼备的实际需求。
查托帕德海与祖克曼的贡献在于提出了首个显式构造的两源提取器，该提取器能够处理多项对数级别的最小熵。这一成就不仅极大地推动了随机性理论，而且将之前看似不相关的几个子领域巧妙结合。 他们的核心创新之一在于引入了抗扰动函数（resilient function）的概念。抗扰动函数最早由Ben-Or与Linial于1985年在分布式计算领域提出，主要用于容错机制的设计。在随机性提取领域中，二者发现将这种函数引入使得两源提取器的构造变得可能，这在学界是前所未有的创举。为了实现这一目标，他们设计了一个单调性（monotone）、可以由AC0电路计算且具备优越抗扰动参数的新型抗扰动函数。
这不仅满足了理论上的严苛需求，也为实际计算模型提供了高效实现的可能性。 进一步地，两源提取器的构造通过把设计出的抗扰动函数与“种子非篡改提取器（seeded non-malleable extractor）”和“无偏采样器（oblivious sampler）”相结合得以完成。这三个组件的巧妙组合，保证了从两个低质量、相互独立的随机源中能稳定地提取出近似均匀的随机比特。 在数学分析层面，他们利用了布拉弗曼（Braverman）对AC0电路的多项对数级别独立性的伪随机性结果，这一著名理论成果建立了两大伪随机子领域之间的桥梁。正是这种跨领域的融合，使得构造有效的显式两源提取器成为可能。 2025年Gödel奖评审委员会由来自世界顶尖高校和研究所的专家组成，包括来自华沙大学的Mikołaj Bojańczyk，华威大学的Artur Czumaj，以色列理工学院的Yuval Ishai，华盛顿大学的Anna Karlin，牛津大学的Marta Kwiatkowska，以及哥伦比亚大学主席Tim Roughgarden。
从多位评委的学术背景与声誉可见，此奖项高度认可了查托帕德海和祖克曼的研究对整个理论计算机科学的发展具有奠基性意义。 该发现不仅推动了理论计算机科学在随机性与复杂度领域的研究进展，也为后续密码学协议的设计和随机算法的安全性提供了坚实的理论基础。尤其是在大数据、云计算以及分布式系统日益普及的今天，有效地利用低质量随机源进行数据保护和安全通信备受关注。 近年来，随着人工智能、区块链及物联网的发展，安全随机性的需求激增。查托帕德海和祖克曼的工作极大地拓宽了随机性提取器的适用范围，为实现更强大的安全保障奠定了理论支撑。 未来的研究或许将在更加复杂的随机环境下继续改进提取器的效率和适用性，例如多源提取器、非独立源提取器以及在实际硬件环境中的实现等方向。
此外，引入抗扰动函数的创新也有望促进其他计算模型的突破，推动分布式计算和伪随机性研究的深度融合。 总结而言，2025年Gödel奖的颁发不仅仅是对查托帕德海与祖克曼个人学术成就的认可，更象征着随机性提取理论的一次重大飞跃。该成就凝聚了多年的理论积累和跨学科整合，为计算机科学的随机性问题提供了创新且实用的解决方案。未来，相关领域的研究者们将在此基础上，持续探索和拓展随机算法的边界，推动信息技术的更加安全和高效发展。
