使用数学理论找到算法的真正潜能

弗吉尼亚·威廉姆斯（Virginia Williams）使用数学理论哄骗算法运行得更快，或证明它们已经达到了最高速度。

每学期，弗吉尼亚大学副教授弗吉尼亚·瓦西里夫斯卡·威廉姆斯（Virginia Vassilevska Williams）试图向其计算机科学专业的本科生传授一门基础课：数学是一切的基础。

通常，学生会参加Williams的6.006课程（算法简介），他们希望学习能够支持最新，最出色的计算技术的高级编程。相反，她的课程重点是如何围绕核心数学模型和概念设计算法。

弗吉尼亚·威廉姆斯。

“当参加算法课时，许多学生期望学习很多程序，也许会使用深度学习，但这是非常数学的，几乎没有编程，”威廉姆斯，史蒂芬·G·史蒂芬（1968）和瑞妮·芬恩（Renee Finn）的职业发展教授说。电气工程和计算机科学系的终身教职。“我们上课的时间不多（每周只有两个小时），但我希望在那段时间里，他们能看到一些数学的美，因为数学使您可以了解如何以及为什么所有的东西都可以一起工作。这确实是一件美丽的事情。”

威廉姆斯的生活很大程度上取决于数学。作为两个数学家父母的孩子，她很早就爱上了这个主题。但是，即使她在该学科上表现出色，她的高中课程还是侧重于德语，写作和生物学。回到大学及以后的初恋时，她运用自己的数学技能在计算机科学领域掀起了波澜。

在极具影响力的工作中，威廉姆斯（Williams）在2012年改进了“矩阵乘法”的算法，该算法是整个计算机科学的基本运算，被认为是24年来最快的迭代。多年后，她与人共同创立了一个新兴领域，称为“细粒度复杂性”，旨在部分解释某些算法可以多快地解决各种问题。

她说，在矩阵乘法中，她的工作现在已略有转移，以表明现有技术“无法做得更好”。“我们再也无法提高自己算法的性能，因此我们想出了一些方法来解释为什么我们不能以及为什么其他方法也无法提高性能。”

通往数学之路

威廉姆斯在保加利亚的索非亚长大，他热爱数学，并且是一名才华横溢的学生。但是她的父母经常提醒她，这位数学家的生活并不完全光鲜亮丽-特别是在试图为两个人在同一地区找到教师演出的时候。他们有时会去工作带他们去的地方。

其中包括小时候在美国各地进行的短暂冒险。第一站是怀俄明州的拉勒米。她的父母是怀俄明大学的客座教授，而威廉姆斯最初由于语言障碍而苦读四年级。“我不是真的会说英语，而是被扔进了这所学校。我和弟弟在迪斯尼频道上观看英语，这非常有趣。”威廉姆斯说，他如今会说保加利亚语，英语，德语和一些俄语。

下一站是洛杉矶-就在罗德尼·金（Rodney King）骚乱发生之时。“我们街道另一边的房子着火了，”威廉姆斯回忆道。“那些是对洛杉矶的一些非常奇怪的记忆。”

两年后返回保加利亚，威廉姆斯决定在数学之外“探索自己的选择”，就读索非亚的德国高中，索菲亚当时是该国的顶尖高中，在那里她学习了德语，文学，历史等专业。人文学科。但是，当涉及到申请大学时，她永远无法动摇她的初恋。“我真的很喜欢人文学科，如今我所学的知识对我非常有帮助。但是这些主题对我来说很难。我的大脑不能那样工作，”她说。“我回到了自己喜欢的地方。”

通过算法穿透

威廉姆斯（Williams）于1999年加入加州理工学院。在大二的那年，她被一个激动人心的新领域迷住了：计算机科学。她说：“我参加了第一门编程课程，而且我很喜欢。”

她被矩阵乘法算法所困扰，矩阵乘法算法的核心是一些重型数学。这些算法计算对应于某些数据的多个数字数组，并输出具有某些目标值的单个组合矩阵。应用范围广泛，包括计算机图形，产品设计，人工智能和生物技术。

博士学位她是卡内基·梅隆大学（Carnegie Mellon）以及其他学院的学生，她发表了许多论文，主题涉及在特殊的代数结构中开发快速矩阵乘法算法，其应用包括飞行调度和网络路由。在获得博士学位后，她在高级研究所，加州大学伯克利分校和斯坦福大学担任了一系列博士后和研究员的职位，并于2013年在算法教学课程中担任教职。

在2012年，她开发了一种新算法，该算法比Coppersmith-Winograd算法要快，后者自1980年代以来在矩阵乘法领域一直处于领先地位。威廉姆斯（Williams）的方法减少了乘法矩阵所需的步骤。她的算法仅比当前的记录保持者慢一点。

处理复杂性

在2010年至2015年之间，威廉姆斯和她的丈夫瑞安·威廉姆斯（Ryan Williams）也是麻省理工学院的教授，成为“细粒度复杂性”的主要创始人。较老的“计算复杂性”领域基于可解决问题的计算步骤的阈值，找到了可证明有效的算法和可能效率不高的算法。

细粒度的复杂度通过计算等效性将问题分组在一起，以更好地证明算法是否真正最优。例如，两个问题可能在解决方式和算法解决这些问题的步骤上看起来非常不同。但是细粒度的复杂性表明，此类问题在秘密上是相同的。因此，如果针对一个使用较少步骤的问题存在一种算法，则必须存在针对使用较少步骤的另一个问题的算法，反之亦然。另一方面，如果存在针对一个问题的可证明的最佳算法，则所有等效问题都必须具有最佳算法。如果有人找到了一个更快的算法来解决一个问题，那么所有等价的问题都可以更快地解决。

威廉姆斯说，自从共同发起该领域以来，“它迅速膨胀了”。“对于大多数理论上的计算机科学会议，您现在都可以在“细粒度的复杂性”标题下提交论文。

2017年，威廉姆斯来到麻省理工学院（MIT），她说她找到了充满激情，志同道合的研究人员。例如，许多研究生和同事正在研究与细粒度的复杂性有关的主题。反过来，她的学生向她介绍了其他学科，例如密码学，现在她在其中介绍了细粒度复杂性的想法。

她有时还会研究“计算社会选择”，这一领域在研究生院期间引起了她的注意。她的工作重点是研究安装体育游戏，投票方案以及将竞争对手放在成对方括号中的其他系统所需的计算复杂性。例如，如果有人知道哪个玩家将在配对比赛中获胜，那么锦标赛组织者可以将所有玩家放在初始种子中的特定位置，以确保某个玩家赢得全部比赛。

模拟所有可能的组合以绑定这些方案可能在计算上非常复杂。但是，狂热的网球选手威廉姆斯（Williams）撰写了2010年的论文（PDF），发现根据单人淘汰赛的比赛安排相当简单，这样，根据对比赛获胜者的准确预测以及其他因素，确定一名选手会获胜。

今年，她与他人合写了一篇论文（PDF），该论文显示锦标赛组织者可以安排初始种子并贿赂某些顶级球员（在特定预算之内），以确保最喜欢的球员赢得比赛。威廉姆斯说：“当我需要从平时的工作中休息时，我会在这一领域工作。”“这是一个有趣的变化。”

得益于当今无处不在的计算技术，威廉姆斯的研究生进入她的课堂的计算机科学领域比她年龄大得多。但是为了帮助他们走上一条独特的道路，她从自己的大学经历中汲取了灵感，并迷上了今天仍在追求的特定主题。

威廉姆斯说：“为了做好研究，您必须沉迷于一个问题。”“我希望他们在我的课程中找到可以困扰的东西。”