发现算法的真正潜力

每学期，副教授维吉尼亚·瓦西列夫斯卡·威廉姆斯(Virginia Vassilevska Williams)都试图向她的计算机科学本科生传授一门基础课程:数学是一切的基础。

通常，学生们来到Williams的课程6.006(算法导论)，想要深入研究高级编程，为最新、最好的计算技术提供动力。相反，她的课程侧重于如何围绕核心数学模型和概念设计算法。 

威廉姆斯最近获得了电气工程和计算机科学系的终身教授职位。他说:“在学习算法课程时，许多学生希望编写大量的程序，或许还希望使用深度学习，但这门课非常数学化，几乎没有编程。”“我们在课堂上没有太多的时间在一起(每周只有两个小时)，但我希望在这段时间里他们能看到一点数学的美——因为数学让你看到所有东西是如何以及为什么一起工作的。”这真是一件美丽的事情。”

威廉姆斯的生活在很大程度上受到数学的影响。作为两个数学家家庭的孩子，她很早就爱上了这门学科。但是，尽管她在这门课上成绩优异，她的高中课程却集中在德语、写作和生物上。回到大学及以后的初恋，她运用自己的数学技能在计算机科学领域掀起波澜。

2012年，在一项极具影响力的工作中，威廉姆斯改进了“矩阵乘法”的算法——这是一种跨计算机科学的基本运算——被认为是24年来最快的迭代。几年后，她与人共同创立了一个名为“细粒度复杂性”的新兴领域，该领域试图在一定程度上解释某些算法解决各种问题的速度有多快。

她说，在矩阵乘法方面，她的工作现在有了轻微的转变，显示现有的技术“不能做得更好”。“我们不能再提高我们自己算法的性能了，所以我们想出了一些方法来解释为什么我们不能，为什么其他方法也不能提高性能。”

数学弯曲路径

威廉姆斯在保加利亚首都索非亚长大，热爱数学，是一名天才学生。但她的父母经常提醒她，这位数学家的生活并不完全是光鲜亮丽的——尤其是当她试图找到两个人在同一领域的教职工作时。他们有时到工作需要他们去的地方旅行。

其中包括小时候在美国的短暂旅行。第一站是怀俄明州的拉勒米。她的父母是怀俄明大学(University of Wyoming)的客座教授。“我真的不会说英语，被扔进了这所学校。我哥哥和我是通过看迪斯尼频道学的英语，那很有趣，”威廉姆斯说，他现在会说保加利亚语、英语、德语和一些俄语。

下一站是洛杉矶——就在罗德尼·金暴动前后。“我们街道另一边的房子着火了，”威廉姆斯回忆道。“那些是洛杉矶非常奇怪的回忆。”

两年后回到保加利亚，威廉姆斯决定在数学之外“探索自己的选择”，就读于保加利亚当时最好的高中——索非亚的德语高中，在那里她学习了德语、文学、历史和其他人文学科。但是，在申请大学的时候，她从来没有动摇过她的初恋。“我真的很喜欢人文学科，我所学到的东西对我现在很有帮助。但是那些科目对我来说很难。我的大脑不是这样工作的，”她说。“我回到了我喜欢的地方。”

被算法

1999年，威廉姆斯进入加州理工学院。在她大二的时候，她被一个令人兴奋的新领域所吸引:计算机科学。“我上了我的第一堂编程课，我很喜欢，”她说。

她被矩阵乘法算法迷住了，这些算法的核心是一些复杂的数学运算。这些算法计算一些数据对应的多个数字数组，并输出一些目标值的单个组合矩阵。应用范围广泛，包括计算机图形学、产品设计、人工智能和生物技术。

在卡耐基梅隆大学读博士时，她发表了大量论文，主题包括开发特殊代数结构中的快速矩阵乘法算法，应用领域包括航班调度和网络路由。在获得博士学位后，她在加州大学伯克利分校(University of California at Berkeley)高级研究所(Institute for Advanced Study)和斯坦福大学(Stanford University)担任了一系列博士后和研究员职位，并于2013年在斯坦福大学获得了一个教授算法课程的教职。

2012年，她开发了一种比Coppersmith-Winograd算法更快的新算法。Williams的方法减少了矩阵相乘所需的步骤。她的算法只比目前的记录保持者稍慢一点。

处理的复杂性

从2010年到2015年，威廉姆斯和她的丈夫、麻省理工学院(MIT)教授瑞安·威廉姆斯(Ryan Williams)成为了“细粒度复杂性”的主要创始人。“计算复杂度”这个较老的领域发现了一些可证明有效的算法和一些可能效率不高的算法，这些算法是基于它们为解决一个问题所采取的一些计算步骤的阈值。

细粒度复杂性通过计算等价性将问题分组，以便更好地证明算法是否真正最优。例如，两个问题在它们所解决的问题以及算法需要多少步来解决它们方面可能会出现很大的不同。但精细的复杂性表明，这些问题其实是一样的。因此，如果一个问题的算法使用更少的步骤，那么一定存在另一个问题的算法使用更少的步骤，反之亦然。另一方面，如果存在一个问题的可证明最优算法，那么所有等价问题都必须有最优算法。如果有人找到了一个更快的算法来解决一个问题，那么所有等价的问题都可以更快地解决。

威廉姆斯说，自从合作开发这个领域以来，“它就像气球一样膨胀起来。”“对于大多数理论计算机科学会议，您现在可以在“细粒度复杂性”标题下提交论文。”

2017年，威廉姆斯来到了麻省理工学院，她说她在那里发现了热情、志同道合的研究人员。例如，许多研究生和同事正在研究与细粒度复杂性相关的主题。作为回报，她的学生向她介绍了其他学科，如密码学，她现在正在从精细的复杂性中引入思想。

她有时也会研究“计算社会选择”，这是她在研究生期间关注的一个领域。她的工作重点是研究操纵体育比赛、投票方案和其他系统所需的计算复杂性，在这些系统中，竞争者被放在成对的括号中。例如，如果有人知道哪位选手将在配对比赛中获胜，比赛组织者可以将所有选手放在初始播种的特定位置，以确保某一位选手赢得全部比赛。

模拟所有可能的组合来装配这些方案可能是非常复杂的计算。但狂热的网球运动员威廉姆斯(Williams)在2010年发表的一篇论文中发现，操纵一场淘汰赛，让某个选手获胜相当简单，这取决于对比赛获胜者的准确预测和其他因素。

今年，她与人合写了一篇论文，表明赛事组织者可以在一定的预算范围内，安排初步的种子比赛，并贿赂某些顶尖选手，以确保自己喜欢的选手赢得比赛。威廉姆斯说:“当我需要从日常工作中休息时，我就会在这个领域工作。”“这是一种有趣的节奏变化。”

多亏了今天无处不在的计算机技术，威廉姆斯的研究生们经常进入她的课堂，他们在计算机科学方面的经验要比她在他们这个年龄时丰富得多。但为了帮助他们走上一条独特的道路，她从自己的大学经历中获得灵感，对她今天仍在追求的特定主题着迷。

“为了做好研究，你必须专注于一个问题，”威廉姆斯说。“我希望他们能在我的课程中找到让他们着迷的东西。”