图灵奖得主 Avi Wigderson 小传

原文：https://amturing.acm.org/award_winners/wigderson_3844537.cfm

作者：Lance Fortnow

译者：Kurt Pan

嘉奖Avi Wigderson：对计算理论的基础性贡献，包括重塑我们对随机性在计算和数学中的作用的理解，以及他数十年来在理论计算机科学领域的智识领导力。

Avi Wigderson 于1956年出生，父母是纳粹大屠杀幸存者。他与两个兄弟在以色列海法靠近海滩的地方长大。完成义务兵役后，Wigderson 于1977年加入了当时刚刚成立不久的海法理工学院（Technion）的计算机科学系。在以色列，计算机科学是以数学为根基的，该系的教授，尤其是 Shimon Even，激发了他对理论计算机科学的兴趣。在海法理工学院，他遇到了未来的妻子 Edna Rothenstein，两人日后育有三名子女。

Wigderson 于1983年在普林斯顿大学获得博士学位，导师是 Richard Lipton。之后，他在加州大学伯克利分校和IBM位于圣何塞的研究中心从事博士后研究工作，随后加入了耶路撒冷希伯来大学的教职。

上世纪70年代是理论计算机科学激动人心的发展时期。Avi Wigderson 很快就在这个领域建立了自己的研究生涯，他将这一年代中形成的诸多思想引领向全新的方向。

理解困难问题

假设你被要求在一个社交网络中找到由200人组成的完全互为朋友的群体——即一个200人的“团”（clique）。你也许会尝试检查所有200人组合的可能性，但数量如此巨大，以至于所需时间超乎想象。这一难题正是计算机科学中著名的 P 与 NP 问题的核心。

P vs NP 问题问到：是否存在一种高效算法，可以解决诸如寻找团、寻找访问不同城市的最短环线、或在地图上用三种颜色给国家上色并确保相邻国家颜色不同等问题。事实表明，如果你对其中一个 NP 问题有快速算法，那么对所有 NP 问题也都可以快速求解。自从上世纪70年代 Steve Cook、Leonid Levin 和 Richard Karp 提出 P 与 NP 问题以来，研究者们始终无法确定这些问题是否能被高效解决。

Avi Wigderson 的许多研究灵感都来自 P 与 NP 问题。他采用了一种基于电路复杂度的研究路径——若能证明 NP 问题无法由小型电路计算，就能证明它们的困难性。

1990年，Wigderson 与 Mauricio Karchmer 找到了电路复杂度与通信复杂度之间的非凡联系。在通信复杂度中，两方各自拥有输入的一部分，他们希望以尽可能少的信息交换来回答一个关于输入的问题。他们构造了一个特定的通信问题，用于体现电路的深度——即信号通过电路的最长路径所需的时间。这一方法为理解电路的能力极限提供了新的视角。

数年后，Wigderson 利用这些工具研究完美匹配问题，即确定一组人是否能两两配对，使得每对中的人都是朋友。与 Ran Raz 合作时，Wigderson 证明了寻找完美匹配无法通过不含非门（NOT门）的小深度电路来实现。而在1986年与 Richard Karp 和 Eli Upfal 的合作中，他又展示了匹配问题可以在并行环境下高效求解，也就是说，如果允许使用 NOT 门，小深度电路就能解决匹配问题。这个成果充分显示了“取非”在加速计算中的强大威力。

通用密码学

20世纪70年代末与80年代初是密码学的变革性时代，这一时期的研究使“这门古老的艺术变成了一门科学”。此类成果分别获得了三次图灵奖：Whitfield Diffie 和 Martin Hellman；Ronald Rivest、Adi Shamir 和 Len Adleman；以及 Shafi Goldwasser 和 Silvio Micali。他们的工作为现代密码学奠定了数学基础，从而衍生出安全加密方法，并为如安全在线投票、远程电话打牌以及在不透露个人薪资的前提下计算平均工资等应用提供了协议。然而，这些解决方案往往依然是针对特定应用的设计。

上世纪80年代，Wigderson 将这些工作推向了更高层次，开发了适用于广泛应用的一般方法。他与 Oded Goldreich 和 Silvio Micali 展示了所有的验证问题都可以有“零知识”证明。例如，若 Bob 正在尝试解数独，Alice 知道答案，她可以在不透露任何解题步骤的情况下，让 Bob 高度确信答案的确存在。这种技术适用于所有 NP 问题，包括旅行商问题和地图三着色问题。之后的研究者在这些理念基础上建立协议，实现了在不暴露秘密密钥的前提下进行身份认证——这对信用卡上的安全芯片极为关键。同一团队还设计了首个通用方法，使得在线进行隐藏信息的游戏（如扑克、桥牌或复杂拍卖）可以公平、安全地进行，即使有少数作弊玩家试图合谋也无妨。

驯服随机性

与在复杂性与密码学方面的工作类似，Wigderson 在概率计算领域的贡献也建立在上世纪70年代的奠基性研究之上。

设想需要检验一个数是否为素数，这在现代密码协议中至关重要。你可以尝试所有可能的因子，但对于大数而言，因子过多，耗时过长。上世纪70年代，Robert Solovay、Volker Strassen 等人开发了高效的随机化素性测试算法，而 John Gill 则为概率计算建立了完整的复杂性理论。

实际上，计算机并不会真正去掷硬币，而是通过复杂函数的输出生成“伪随机数”。这些伪随机生成器在当时尚未有坚实的理论基础，多为临时特设构造。

在20世纪80年代末，Wigderson 与同事们发现了一种基于计算困难函数构造伪随机生成器的形式化方法。Wigderson 与 Noam Nisan、Russell Impagliazzo 以及其他学者在一系列论文中展示了如何利用合适的困难函数来产生强伪随机生成器，使其输出与真实随机比特计算不可区分。这种输出可以替代任何概率性算法中所需的随机性。

进入21世纪后，身为普林斯顿高等研究院教授的 Avi Wigderson 继续推进着对随机性的理解。想象将若干城市用最少的道路相连，这样当你在每个城市随机选择一条出路时，很快便能到达一个完全随机的城市。这类网络被称作“扩张图”（expander graphs） 。Wigderson 与 Omer Reingold、Salil Vadhan 一起发展出了一种新的“之字形”递归构造方法来生成扩张图，这种方法巧妙优雅，证明亦简单明了。

这种“之字形”构造催生了一种算法，它能用很少的内存判断地图上两个城市是否连通。Reingold 的算法利用“之字形”构造使得已连接的城市变得“距离很近”，从而在这张新地图中，只需检查从一个城市出发的所有短途行程，便可判断是否能到达另一个城市。

扩张图还可应用于纠错码技术。当通过无线链路传输信息时，比特可能会被干扰导致出错。使用纠错码，发送方将信息加以适当扩展，使接收方即便少量字符被篡改也能恢复原文。给出扩张图更强的界，能带来更高效的纠错码。

扩张图还可用来从弱随机源中提取高质量的随机性。设想你需要真随机的比特，但你能获得的只是诸如太阳黑子活动的数据。这些数据虽有波动，但远称不上均匀随机。通过多篇论文与众多合作者，Wigderson 找到了实现这一目标的方法：或通过加入少量额外随机性，或使用多个独立的弱随机源来获得强随机性。

Wigderson 的解决方案往往可以应用于看似无关的问题。以拉姆齐图（Ramsey graph） 为例，这是一种网络结构，这里不存在中等规模的群体能做到全部互为朋友或全部互非朋友。Wigderson 和他的后续研究者所发展的提取器技术，为构造拉姆齐图提供了新的方法，提升了这些图中满足既非全连接也非全部链接的的群体大小上限。

Wigderson 的遗产

此处讨论的研究仅是 Avi Wigderson 广泛工作的一小部分。他在理论计算机科学两大顶级会议——ACM STOC和 IEEE FOCS 上发表论文超过百篇，数量比其他任何研究者都多。此外，Wigderson 很少独自工作，他与近200位不同的合作者有过合作。

1999年，Wigderson 加入普林斯顿高等研究院担任数学学部 Herbert H. Maass 讲席教授。几乎在他加入的同时，IAS 就成为了计算复杂性研究的中心，Wigderson 在此接待访问学生、博士后及访问学者。许多当今该领域的领军人物都在高等研究院磨练了技能。

Wigderson 曾任西蒙斯基金会（Simons Foundation）的科学咨询委员会成员，他的倡议促成了加州伯克利西蒙斯计算理论研究院的成立，使其成为理论学界又一重要中心。

2019年，Wigderson 在普林斯顿大学出版社出版了《Mathematics and Computation: A Theory Revolutionizing Technology and Science》一书。他在书中指出，P与NP 问题、计算复杂性以及更广泛的理论计算机科学不仅对计算机科学至关重要，还对生物学、经济学、物理学及社会科学等领域有着核心哲学意义。尽管如此，他也从未拒绝将该领域视为严肃的数学学科。当有人建议算法的实现者应与算法发现者享有同等的荣誉时，Wigderson 机敏地回应道：“那就让他们先做吧。”