发布时间：2024-05-11 16:50:32 栏目：生活
ACM(计算机协会)今天任命 Avi Wigderson 为 2023 年 ACM AM 图灵奖获得者，以表彰他对计算理论的基础性贡献，包括重塑我们对随机性在计算中的作用的理解，以及他数十年来在理论计算机科学。
维格德森是新泽西州普林斯顿高等研究院数学学院的赫伯特·H·马斯教授。他是计算复杂性理论、算法和优化、随机性和密码学、并行和分布式计算、组合学和图论以及理论计算机科学与数学和科学之间的联系等领域的领军人物。
ACM AM 图灵奖通常被称为“计算机领域的诺贝尔奖”，奖金为 100 万美元，由 Google, Inc. 提供资金支持。该奖项以英国数学家艾伦·图灵 (Alan M. Turing) 的名字命名，他阐述了数学基础的计算。
什么是理论计算机科学?
理论计算机科学涉及该领域的数学基础。它提出了诸如“这个问题可以通过计算解决吗?”之类的问题。或者“如果这个问题可以通过计算解决，需要多少时间和其他资源?”
理论计算机科学还探索高效算法的设计。每一项影响我们生活的计算技术都是通过算法实现的。了解强大而高效的算法的原理不仅可以加深我们对计算机科学的理解，还可以加深我们对自然法则的理解。虽然理论计算机科学被认为是一个提出令人兴奋的智力挑战的领域，并且通常不直接涉及改进计算的实际应用，但该学科的研究突破已经导致了该领域几乎每个领域的进步——从密码学到计算生物学网络设计、机器学习和量子计算。
为什么随机性很重要?
从根本上来说，计算机是确定性系统。应用于任何给定输入的算法的指令集唯一地确定其计算，特别是其输出。换句话说，确定性算法遵循可预测的模式。相比之下，随机性缺乏明确的模式，或者事件或结果的可预测性。由于我们生活的世界似乎充满了随机事件(天气系统、生物和量子现象等)，计算机科学家通过允许算法在计算过程中做出随机选择来丰富算法，以期提高算法的效率。事实上，许多尚无有效的确定性算法的问题已经可以通过概率算法有效地解决，尽管误差概率很小(可以有效地减少)。但随机性是必不可少的还是可以消除的?概率算法成功所需的随机性质量是多少?
这些以及许多其他基本问题是理解计算中的随机性和伪随机性的核心。对计算中随机性动态的更好理解可以使我们开发出更好的算法，并加深我们对计算本身本质的理解。
威格德森的贡献
四十年来，威格德森一直是理论计算机科学研究的领导者，他为理解随机性和伪随机性在计算中的作用做出了基础性贡献。
计算机科学家发现随机性和计算难度(即识别没有有效算法的自然问题)之间存在显着的联系。威格德森与同事合作，撰写了一系列极具影响力的关于用硬度换取随机性的著作。他们证明，在标准且广泛相信的计算假设下，每个概率多项式时间算法都可以有效地去随机化(即完全确定性)。换句话说，随机性对于高效计算来说并不是必需的。这一系列作品彻底改变了我们对随机性在计算中的作用的理解，以及我们思考随机性的方式。该系列有影响力的论文包括以下三篇：
- “硬度与随机性”(与 Noam Nisan 合着)
除其他发现外，本文引入了一种新型伪随机生成器，并证明在比之前已知的假设弱得多的假设下，可以对随机算法进行有效的确定性模拟。
-“除非 EXPTIME 有可发布的证明，否则 BPP 具有次指数时间模拟”(与 László Babai、Lance Fortnow 和 Noam Nisan 合着)本文使用“硬度放大”来证明可以模拟有界误差概率多项式时间 (BPP)在较弱的假设下，在次指数时间内无限多个输入长度。
本文介绍了一种更强的伪随机生成器，具有本质上最佳的硬度与随机性权衡。
重要的是，Wigderson 这三篇论文的影响远远超出了随机性和去随机化领域。这些论文的想法随后被应用于理论计算机科学的许多领域，并导致该领域的几位领军人物发表了有影响力的论文。
Wigderson仍然致力于计算中随机性的广泛领域，在与 Omer Reingold、Salil Vadhan 和 Michael Capalbo 合作的论文中，Wigderson 给出了扩展图的第一个有效组合构造，这些扩展图是具有强大连通性的稀疏图。它们在数学和理论计算机科学中都有许多重要的应用。
免责声明：本文由用户上传，如有侵权请联系删除！
