从2023年图灵奖获得者Avi Wigderson看普林斯顿大学数学系的崛起

来源：数学大院

美国计算机协会（ACM）现指定Avi Wigderson为2023年ACM A.M.图灵奖获得者，以表彰他对计算理论的奠基性贡献，包括重塑我们对随机性在计算中的作用的理解，以及他数十年来对理论计算机科学领域的引领。

Wigderson

Wigderson担任新泽西州普林斯顿高等研究院数学学院Herbert H. Maass教授。他一直是计算复杂性理论、算法和优化、随机性和密码学、分布式并行计算、组合学、图论以及理论计算机科学与数学和科学之间的联系等领域的领军人物。

ACM A.M.图灵奖通常被称为“诺贝尔计算机奖”，奖金为100万美元，由谷歌公司提供资金支持。该奖项以阐明计算的数学基础的英国数学家艾伦·麦席森·图灵命名。

Wigderson的贡献

四十年来，Wigderson作为理论计算机科学研究领域的领军人物，对理解随机性和伪随机性在计算中的作用做出了奠基性贡献。

计算机科学家发现随机性与计算难度（即识别没有高效算法的自然问题）之间有显著联系。Wigderson与同事合作撰写了一系列极具影响力的关于用难度换取随机性的著作。他们证明，在标准、广泛认可的计算假设下，每一种概率多项式时间算法都可以有效去随机化（即完全确定）。换句话说，随机性并不是高效计算的必要条件。该系列著作彻底改变了我们对随机性在计算中的作用的理解，以及我们思考随机性的方式。该系列有影响力的论文包括以下三篇：

• “难度与随机性”（与 Noam Nisan 合著）

  除其他发现外，该论文还介绍了一种新型伪随机发生器，并证明了在比以前所知更弱的假设下，可以对随机算法进行高效确定性模拟。
  

• “除非指数时间有可发布的证明，否则BPP有亚指数时间模拟”（与 László Babai、Lance Fortnow 和 Noam Nisan 合著）

  该论文利用“难度放大”证明在弱假设下可以在亚指数时间内模拟无限多输入长度的有限错误概率多项式时间（BPP）。
  

• “P=BPP（如果E需要指数电路）：将XOR Lemma去随机化”（与Russell Impagliazzo合著）
  该论文介绍一种更强的伪随机发生器，其在本质上实现了难度与随机性之间的最优权衡。

重要的是，Wigderson的这三篇论文的影响远远超出了随机性和去随机化领域。这些论文中的观点随后被应用于理论计算机科学的许多领域，并引领该领域多位领军人物发表有影响力的论文。

Wigderson仍然在计算随机性的广泛领域开展工作，在他与Omer Reingold、Salil Vadhan和Michael Capalbo合著的论文中首次提出了扩展图的高效组合构造，该扩展图是具有强连接特性的稀疏图。它们在数学和理论计算机科学领域都有许多重要应用。

除随机性方面的工作以外，Wigderson还是理论计算机科学的其他多个领域的知识领袖，包括多验证人交互式证明、密码学和电路复杂性。

Wigderson

指 导

除开创性技术贡献以外，Wigderson还是一位广受尊敬的导师和同事，指导过无数年轻研究人员。他广博的知识和出众的技术能力，再加上他的友善、热情和慷慨，吸引了许多最优秀的年轻人投身于理论计算机科学领域。

“必须指出的是，Avi Wigderson还获得了阿贝尔奖，该奖项被认为是数学领域最重要的终身成就荣誉，”ACM总裁Yannis Ioannidis解释说。“获得ACM A.M.图灵奖是水到渠成的——因为数学是计算机科学的基础，而Wigderson的工作将广泛的数学子领域与理论计算机科学联系在一起。Wigderson代表理论计算机科学领域的强大的知识力量，这门令人兴奋的学科吸引了一些最有前途的年轻研究人员来攻克最艰巨的挑战。今年的图灵奖表彰Wigderson在随机性方面的具体工作，以及他对整个理论计算机科学领域产生的间接但实质的影响。

“在过去三十年里，Avi Wigderson在随机性和其他课题方面的工作决定了理论计算机科学的研究方向，”谷歌高级副总裁 Jeff Dean 解释说。“从计算机科学诞生之初，研究人员就已认识到，结合随机性是为广泛应用设计更快算法的一种方法。努力更好地理解随机性将继续为我们的领域带来重要益处。谷歌还向Wigderson的导师角色致敬。他的同事们认为他提出了伟大的想法和研究方向，并激励着新一代聪明的年轻研究人员为之努力。我们祝贺Avi Wigderson获得ACM A.M.图灵奖这一计算机领域的最高荣誉。”

Reference

• 难度与随机性
  https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf

• 除非指数时间有可发布的证明，否则BPP有亚指数时间模拟

  https://link.springer.com/article/10.1007/BF01275486

• P=BPP（如果E需要指数电路）：将XOR Lemma去随机化

  https://dl.acm.org/doi/pdf/10.1145/258533.258590

下面通过王则柯编写的文章看普林斯顿数学系是如何崛起的。

一流的学术机构给学生提供最好的环境，是不是能够利用这个环境，是研究生自己的事情。

王则柯｜撰文

普林斯顿大学数学系和普林斯顿高等研究院数学部，在20世纪30和40年代迅速成为美国学术界冉冉上升的明星，不仅在拓扑学、代数学和数论方面独占鳌头，计算机理论、运筹学和新生的博弈论也处于领先地位。第二次世界大战以后，大家都返回普林斯顿，科学和数学被视为战后创造更加美好的世界的关键。

由于数学在战争年代对于美国的贡献，政府似乎突然意识到纯粹研究的重要性，军方尤其如此，纷纷拨款资助纯粹理论方面的研究项目。人们充满热情地筹划举办新的一届世界数学家大会，而上一届大会是在战前的阴郁日子里召开的。

人才优先——普林斯顿高等研究院的创立

美国新泽西州班伯格家族，自从白手起家在家乡纽沃克市开设第一家小商店以来，经过多年发展，跃升为美国百货零售业巨子，老板是两兄妹。

不知是出于敏锐的商业直觉抑或纯属鬼使神差的巧合，在1929年纽约股市全面崩溃之前的6个星期，他们将手中持有的股票全部抛出兑现，躲过了这场没顶的"世纪之灾"。当时他们掌握的财富达到2500万美元，决定在新泽西州捐资做一些善事。

他们原本打算资助一所牙医学校，但是医学教育专家亚伯拉罕·弗雷克斯纳成功地说服他们放弃了这个想法，转而创立一所一流的研究机构，那里将没有教师，没有学生，没有课程，只有不必为谋生操心的研究人员。

至于研究专业，弗雷克斯纳自己倾向于经济学，不过很快就听取了别人的建议，选择数学这样一门更加具有基础性质的学科。事实上，那时候和现在一样，鉴别优秀的数学家远比挑选出色的经济学家更加容易。 接下来就要考虑选址问题。班伯格家族所在的纽沃克市只有油漆工厂和屠宰场，弗雷克斯纳希望邀请的国际学术明星们当然不会乐意跑到这样的地方来。

于是，邻近的普林斯顿自然成为第二选择。据说还是拓扑学家奥斯瓦尔德·维布伦告诉班伯格家族，说普林斯顿完全可以"从拓扑学意义上"被认为是纽沃克市的"郊区"，这才促使他们下了最后决心。大家知道，作为几何学的升华，拓扑学讲究邻近关系，但是不计较距离。 弗雷克斯纳怀里揣着班伯格家族提供的资金，开始周游世界，招募优秀学者，许诺给予他们优厚工资和额外津贴，并且保证他们拥有绝对的自由和独立性。

当时，希特勒刚刚开始执掌德国政府，德国大学大量排挤犹太人，战争阴云日益临近，整个欧洲都显得忧心忡忡。经过长达三年的耐心的讨论，欧洲最伟大的学者爱因斯坦终于同意成为普林斯顿高等研究院数学部的第二名成员。对此，他的一个朋友评论说，"物理学的教皇已经移居美国，美国很快就会成为世界自然科学中心"。1933年，奥地利维也纳的逻辑学神童库尔特·戈德尔和德国数学巨星赫尔曼·外尔随后来到美国。

外尔在接受邀请的时候提出了一个条件，要求研究院同样为下一代学者打开大门。这样，刚满30岁的冯·诺伊曼因此获得聘请，成为研究院最年轻的教授。几乎是在一夜之间，普林斯顿成为像哥廷根大学一样引人注目的学术圣地。 研究院的富尔德大楼在1939年落成。原本与普林斯顿大学的同事们一起在数学系所在的范氏大楼工作的这些教授，有了自己的地方。

不过，那时研究院的学者已经和大学教授们成为好朋友，他们合作开展研究项目，联合编辑学刊，出席彼此的讲座，参加研讨会，还一起享受下午茶。这种亲密的友谊并没有因为搬家而有所削弱。研究院和大学的交往是相得益彰的：研究院的声誉将最出色的教师和学生吸引到大学来，同时，大学里相当活跃的数学系和物理学系也引起了研究院的访问学者或研究人员的强烈兴趣。

与普林斯顿的蓬勃发展相反，一度被视为美国数学界掌上明珠的哈佛大学在40年代失去了昔日的光辉。传奇校长G·D·伯克霍夫去世，包括马歇尔·斯通、马尔斯顿·摩尔斯和哈斯利·惠特尼在内的一部分最优秀的年轻学者相继离开，其中两人转投普林斯顿高等研究院。

爱因斯坦曾经在研究院公开抱怨伯克霍夫是世界上最有名的反犹太人学者，不论这是否属实，伯克霍夫确实对犹太人抱有偏见，使他不能吸收逃离纳粹德国的犹太人精英。同时，哈佛也忽略了当代最伟大的美国数学家诺尔伯特·维纳，他建立了平稳时间序列预测理论和现代控制论科学。因为他也是犹太人。结果，诺尔伯特·维纳去了一街之隔的、当时被学界夸大地说成比卡内基工学院的水平高不了多少的麻省理工学院。

说起亚伯拉罕·弗雷克斯纳出任普林斯顿高等研究院，还有一段人类文明的有趣故事：丈夫不如妻子那样了解自己。当班伯格兄妹成功地从股票市场抽调资金准备为家乡和国家做一点善事的时候，他们委托两位律师去找亚伯拉罕·弗雷克斯纳。那时候弗雷克斯纳已经退休。

班伯格之所以要找20世纪初年美国著名的教育家弗雷克斯纳，是因为他写过一份报告，讨论当时的美国医学教育，认为系统混乱，标准不高。长此下去，在20世纪的医学发展中美国要落在后面，这将直接危害美国人民的健康和福利。报告引起朝野的震惊，而美国的医学教育在1910年代也就有了长足的进步。

自此之后，弗雷克斯纳还被洛克菲勒基金会邀请去做其他一些事情，比如捐资开办北京协和医院。 律师找到弗雷克斯纳，对他说，"有一个很有钱的人想捐钱做一些事情。我们知道你对社会事业很热心，很有见解，也很有经验，想听听你的意见"。弗雷克斯纳说，"巧极了，我正好写了一本小册子，你们拿去看看"。小册子的主题，就是指出当时美国在科技方面非常脆弱。

当时，美国的学子要跑到欧洲才能拿到象样的科学学位。弗雷克斯纳指出，这样下去是不行的。小册子指出，美国必须建立一些独立的专门从事科研的机构。他特别推崇德国的制度。 几天以后，律师打电话给弗雷克斯纳，说班伯格先生想请他吃饭。午饭的时候，班伯格对弗雷克斯纳说："你的书写得很好，我愿意尽我的可能支持你的设想和计划。你觉得需要多少钱？"

弗雷克斯纳后来在自传中说，见面之前没有想过真的就可以去做，更没有想过需要多少钱。班伯格一问，他必须马上回答，所以就随便说了一个他认为很大的数字："500万"。500万美元在当时的确是一个惊人的数字。 班伯格当时没有立即确认。几天以后，他给弗雷克斯纳写信说，"我愿意捐500万，但是有一个条件，你必须出山，当高等研究院的第一任院长"。

接信以后，弗雷克斯纳想了好久，不能决定。他一方面因为自己的设想有了实现的机会而高兴，另一方面觉得自己已经退休多时，不应该"东山再起"。就这么烦躁不安地踌躇了十多天。两个星期以后，他的太太对他说："你必须接受。我跟你已经共同生活了几十年，对你非常了解。假如今天你不接受这件事情，你的脾气一定会变得很坏，我就无法再跟你一起生活下去了"。 就这样，亚伯拉罕·弗雷克斯纳成了普林斯顿高等研究院的第一任院长。

作为院长，第一件事情就是筹划研究院应该研究什么东西。500万美元固然是一个很大的数目，但是要想在尖端科技的每个方面都去研究，在文史方面都去研究，还是远远不够的，所以必须作出选择，有所取舍。至于如何选择，弗雷克斯纳定下一条原则：先要物色卓越的人才，然后发展他们擅长的学科，而不是先决定发展什么学科，才去找人。也就是说，先去找已经做出并且还能做出杰出研究工作的人，如果他愿意来的话，就在研究院里开辟他所从事的研究领域。

普林斯顿高等研究院之所以能够很快在国际学界树立地位，弗雷克斯纳先生的这项"人才优先"政策实在是一个关键。

把孩子扔到河里——普林斯顿大学数学系的崛起

1948年秋天，数学系主任所罗门·列夫谢茨教授在西休息室召集所有一年级研究生谈话。他用浓重的法国口音给他们讲述生活的道理，整整讲了一个小时。他的目光锐利，情绪激动，大声说话，还不断用木头假手敲桌子。

他说他们是最优秀的学生，每个人都是经过精心挑选才来到这里来的，但是这里是普林斯顿，是真正的数学家从事真正的数学研究的地方，和这里已经成名的数学家相比，他们只不过是一群无知可怜的娃娃而已，普林斯顿就是要把他们培养成人。

他说他们可以自己决定要不要上课，他不会骂他们，分数没有任何意义，只是用来满足那些"讨厌的教务长"的"把戏"。他对大家的唯一要求就是每天参加下午茶的聚会，在那里他们会见到世界上最了不起的数学家。当然了，如果他们愿意，他允许他们参观高等研究院，看看他们能不能幸运地见到爱因斯坦、戈德尔或者冯·诺伊曼。

他一再重复的一点是，教授们绝对不会把他们当做娃娃。对于年轻研究生们，列夫谢茨的这番话无异于美国作曲家苏萨的鼓舞人心的乐曲。 毫无疑问，列夫谢茨富有企业家精神，精力充沛。他在莫斯科出生，在法国接受教育，酷爱数学，却由于不是法国公民而不能选修数学，只好学习工程学，后来移民美国。

23岁那年，他正在著名的电气公司西屋公司工作，一场严重的变压器爆炸事故发生，夺去了他的双手。用了几年时间，他才得以康复。其间他深感痛苦绝望，不过这场事故最终促使他下定决心，追求自己的真爱——数学。

他到克拉克大学攻读博士学位，那里因为1912年弗洛伊德曾经举办精神分析讲座而闻名。不久，列夫谢茨和那里的另一位数学系学生相爱，两人结为秦晋之好。毕业之后，他在内布拉斯加州和堪萨斯州教了将近10年的书，一直寂寂无名。课余时间他撰写了多篇具有原创思想的精辟的论文，渐渐引起学术界的重视，终于有一天，来自普林斯顿大学的一个电话邀请改变了他的生活道路，他成为普林斯顿大学数学系首批犹太人教师之一。

列夫谢茨身材高大，举止粗暴，衣着毫无品味可言。刚来的时候，因为人们常常在走廊里假装看不见他，避免和他打招呼，他常常自称为"看不见的人"。但是他很快证明自己具有非凡的魄力，可以跨越远比这些过分拘谨、媚上傲下的同事更加困难的障碍，一手将普林斯顿数学系从一个"有教养的平凡之辈"培养成为令人景仰的"巨人"。

列夫谢茨招聘数学家只有一个条件，这就是原创性的研究。他注重独立思考和原创精神高于一切，蔑视那些优美或刻板的证明。据说他从来没有在课堂上做完一个正确的证明。

他的第一部全面论述拓扑学的著作提出了"代数拓扑学"的术语，影响深远，其主要价值在于体系，而不是细节，细节方面的确有很有一些欠斟酌的地方。有人传说他是在"一个休息日"里完成这部著作的，他的学生们根本没有机会帮助他整理。 他了解数学的绝大多数领域，但是他的演讲往往没有条理。他的编辑作风专制而又有个性，使普林斯顿一度令人厌倦的《数学年刊》（Annals of Mathematics）一跃成为世界上最受推崇的学术刊物。

有人批评他将许多犹太学生拒之数学系的门外，他却辩解说这是因为担心他们毕业之后多半找不工作。不过，没有人可以否认他确实具有极佳的判断力。他训斥别人，独断专行，有时相当粗暴，但是他的目标只有一个，就是为数学系赢得世界声誉，将学生们培养成和他自己一样坚韧不拔的真正的数学家。

列夫谢茨关于研究生数学教育的思想是以德国和法国名校的传统为基础的，很快就成为普林斯顿的指导纲领，其核心是尽快使学生投入到他们自己的研究工作中去。由于普林斯顿数学系本身就积极从事研究工作，同时有能力对学生进行指导，使列夫谢茨的想法得以付诸实践。

博学固然是一项值得尊敬的才能，但这并不是列夫谢茨的目标，他更强调学生应该有能力提出自己独特的看法，作出重要的原创性的发现。 普林斯顿给予学生最大的压力和最小的管制。列夫谢茨就说过，系里不要求学生非来上课不可。数学系确实设立了自己的一整套课程，不过考勤和分数一样，几乎只是幻象。

到了在学生的成绩报告上打分的时候，一些教授会给所有学生判C，另一些教授则会都给A，装装样子而已。一些学生根本不需要上一节课就可以得到分数。的确，所谓成绩单只是用来讨好那些墨守成规、被称为"俗人"的教务长之辈。比如数学系传统的口试，可能只是要求学生翻译一段法语或德语数学论文。

由于选定的论文充满数学符号，文学极少，即便没有多少外语知识的学生也能看出个大概头绪。如果实在搞不清楚，只要学生许诺回去好好研读这份论文，老师们也可能判他合格。真正要计算成绩的是"总考"，包括5个题目，其中3个由数学系选择，另外2个由考生自行选择，在第一年的年终或第二年进行。

不过，即便是这次考试也可能依据每个学生的具体优缺点而进行设计。举例而言，如果某个学生对一篇论文掌握得很好，而且他总共就知道这一篇论文，那么考官确实有可能大发善心，出题时自觉把内容限制在这篇论文里，好让这个学生顺利通过考试。

学生动笔写毕业论文之前，最重要的事情是要找到一个高资历的教授支持自己选择的题目。整个数学系的教师对学生都相当了解，如果他们认为某个学生实在没有能力完成自己的题目，列夫谢茨就会毫不犹豫地更换导师或干脆叫他离开。因此，通过了总考的学生通常在两三年里就能取得博士学位，而在哈佛则需要六七年，甚至更长的时间。

则柯在1981-1983初次到普林斯顿大学进修的时候，当时的系主任项武忠教授还在津津乐道列夫谢茨建立的传统：普林斯顿数学系把研究生"扔到河里"，游过去的，就成为博士。普林斯顿总是有最好的教授，最好的访问学者，他们授业解惑，可以说是有问必答，但是决不关心考试。如果你自己不思进取，没有人会逼迫你。

普林斯顿总是开最先进的课，每周好几次请世界一流的数学家讲演自己的最新发现。她提供最好的环境，是不是能够利用这个环境，是研究生自己的事情。 至于列夫谢茨，教授们都有点儿夸大地说，正因为他从来没有在课堂上完整地做完一个正确的证明，他的学生不得不把他的漏洞补上，从而练就了本事。

如果教授在课堂上讲的都已经十分正确十分完备，而学生能够把教授所讲背得滚瓜烂熟，那不叫本事。懂得高等教育的人都知道，如果每一步都要讲解得十分完备，你根本不可能在大学讲授一门象样的课程。

本文原载于《我所知道的普林斯顿》，作者系中山大学岭南学院教授。

未来智能实验室的主要工作包括：建立AI智能系统智商评测体系，开展世界人工智能智商评测；开展互联网（城市）大脑研究计划，构建互联网（城市）大脑技术和企业图谱，为提升企业，行业与城市的智能水平服务。每日推荐范围未来科技发展趋势的学习型文章。目前线上平台已收藏上千篇精华前沿科技文章和报告。