计算机理论顶会STOC 2021奖项出炉，滕尚华等华人学者获奖

机器之心报道

编辑：小舟、张倩

近日，全球计算机理论顶会 ACM STOC 公布了今年的最佳论文奖、最佳学生论文奖、时间检验奖等奖项。南加州大学计算机科学与数学系教授滕尚华等多位华人学者获奖。

作为计算机理论领域的全球顶级学术会议，ACM 计算理论年会（ACM Symposium on Theory of Computing，STOC）始于 1969 年，今年已经举办了 53 届。

STOC 在整个计算机科学领域享有崇高的声望，属于公认难度最高的会议之一。与人工智能不同，计算机理论领域被认为是国内学界与全球顶级水平相距较大的方向，在 STOC 大会中，2000-2017 年大陆研究机构平均每年发表的论文数量仅为 0.89 篇。

该会议由 ACM SIGACT (Special Interest Group in Algorithms and Computation Theory) 主办，历年会议涵盖的领域十分广泛，包括算法和数据结构、计算复杂性、密码学、计算几何、组合学、随机与去随机化、算法博弈论和量子计算等。受疫情影响，STOC 2021 于 2021 年 6 月 21-25 日在线举行。

在 STOC 2021 上，南加州大学计算机科学与数学系教授、哥德尔奖得主滕尚华的论文摘得时间检验奖。此外，来自华盛顿大学的 Huijia Lin 参与的论文《Indistinguishability Obfuscation from Well-Founded Assumptions》获最佳论文奖，他们研究的 iO 问题被誉为密码学「皇冠上的明珠」。

以下是 STOC 2021 的具体获奖情况。

最佳论文奖

今年，共有三篇论文摘得 STOC 的最佳论文奖，分别是：

论文 1：A (Slightly) Improved Approximation Algorithm for Metric TSP

作者：Anna R. Karlin（华盛顿大学）、Nathan Klein（华盛顿大学）、Shayan Oveis Gharan（华盛顿大学）

论文链接：https://arxiv.org/pdf/2007.01409.pdf

旅行推销员问题（TSP）是组合优化中最基本的问题之一。在这篇论文中，对于某个

，研究者为度量空间下的旅行推销员问题（metric TSP）给出了一个随机

逼近算法。

论文 2：The Complexity of Gradient Descent: CLS = PPAD ∩ PLS

作者：John Fearnley（利物浦大学）、Paul W. Goldberg（牛津大学）、Alexandros Hollender（牛津大学）、Rahul Savani（利物浦大学）

在这篇论文中，研究者探讨了在有界凸多边形域上能用梯度下降法求解的搜索问题，并证明了这类连续局部搜索（CLS）问题等于两个已知类的交集：PPAD 和 PLS。

论文 3：Indistinguishability Obfuscation from Well-Founded Assumptions

作者：Aayush Jain（加州大学洛杉矶分校）、Huijia Lin（华盛顿大学）、Amit Sahai（加州大学洛杉矶分校）

iO（Indistinguishability Obfuscation，不可区分混淆）是密码学中黑科技一样的存在，它不仅可以隐藏数据集合，还可以隐藏计算机程序的内部工作机制，创造出强大的加密工具。但这种力量的强大让人们怀疑 iO 是否真的存在。

在这篇最佳论文中，研究者首次展示了如何仅使用「标准」安全假设来构建 iO。它从理论角度提供了一种即时构建多个加密工具的方式，而这在之前是不可能的。例如，它允许创建「可否认」加密和「函数」加密。以色列理工学院教授 Yuval Ishai 曾表示：「现在应该不会有人怀疑 iO 的存在了。」（详见：《不可区分混淆被实现，计算机科学家摘得这颗密码学「皇冠上的明珠」）

本文作者之一 Huijia Lin 本科毕业于浙江大学，2011 年在康奈尔大学拿到博士学位，目前在华盛顿大学计算机科学与工程学院担任副教授。她的主要研究兴趣集中在密码学以及密码学与其他计算机领域的交叉领域，如复杂性理论、算法设计和安全等。

最佳学生论文奖

STOC Danny Lewin 最佳学生论文奖是为了纪念著名数学家和企业家 Danny Lewin 设立的，他曾参与创立互联网公司 Akamai Technologies。今年共有两篇论文获得 Danny Lewin 最佳学生论文奖。

论文 1：Discrepancy Minimization via a Self-Balancing Walk

作者：Ryan Alweiss（普林斯顿大学）、Yang P. Liu（斯坦福大学）、Mehtaab Sawhney（麻省理工学院）

该研究探究了在各种设置下

中向量的差异最小化，在多个维度上分析了一个新的简单随机过程。根据研究结果的推论，研究者推算出由 Bansal 等人提出的在线向量平衡中几个问题的对数因子的严格边界，并提出了 Komlós 猜想的对数边界的线性时间算法。

本文作者之一 Yang P. Liu 本科毕业于麻省理工学院，目前在斯坦福大学读博，主攻数学。他曾在 2014 年和 2015 年拿到过国际数学奥林匹克竞赛（IMO）的金奖。除了纯数学之外，他还对理论计算机科学感兴趣，尤其是算法设计。

论文 2：Separating Words and Trace Reconstruction

作者：Zachary Chase（牛津大学）

论文链接：https://dl.acm.org/doi/abs/10.1145/3406325.3451118

该研究证明对于任意不同的 x,y ∈

，存在一个具有 O(n^(1/3)) 状态的确定有限自动机，它接受 x 但不接受 y。这改进了 Robson 在 1989 年提出的 O(n^(2/5)) 边界。使用一种类似的复杂分析技术，研究者改进了最坏情况轨迹重建的上限，表明任何未知字符串 x ∈

都能以高概率从 exp(O(n^(1/5))) 独立生成的迹（trace）中重建。

时间检验奖

今年 STOC 的时间检验奖颁给了 7 篇论文，距今的时间跨度大约分为 30 年、20 年、10 年三个类别，分别是：

论文 1：Completeness theorems for non-cryptographic fault-tolerant distributed computation（STOC 1988）

作者：Michael Ben-Or、Shafi Goldwasser、Avi Wigderson

论文 2：Multiparty unconditionally secure protocols（STOC 1988）

作者：David Chaum、Claude Crépeau、Ivan Damgård

论文 3：Verifiable secret-sharing and multiparty protocols with honest majority

作者：Tal Rabin、Michael Ben-Or

论文 4：A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries（STOC 2001）

作者：Mark Jerrum、Alistair Sinclair、Eric Vigoda

论文 5：Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

作者：Daniel A. Spielman、Shang-Hua Teng

论文 6：Approximate distance oracles

作者：Mikkel Thorup、Uri Zwick

论文 7：The computational complexity of linear optics

作者：Scott Aaronson、Alex Arkhipov

论文 5 的作者之一滕尚华是著名的华人学者。他是南加州大学计算机科学与数学系教授，此次获奖的论文由他和 Daniel A. Spielman 合著。这篇论文在 STOC 2001 上发表，曾获 ACM 算法和计算理论特别兴趣小组的奖项。如今经过 20 年的时间检验，它又摘得 STOC 2021 的时间检验奖。

在这篇论文中，滕教授和 Spielman 使用平滑分析的概念为了解算法性能给出了更实际的理解方法，例如度量其运行时间。这个概念有助于解释一个现象：为什么有些算法在实践中比理论上更有效？该研究发现，许多算法，尤其是广泛使用的线性规划单纯形算法，只要输入中有噪声就可以工作，而现实世界的数据中通常存在噪声。该研究的发现已应用于无数实用算法，涉及互联网通信、深度学习、数据挖掘、差分隐私、博弈论和个性化推荐系统等多个领域。

滕尚华于 1985 年毕业于上海交通大学，获得电气工程和计算机科学双学士学位，1988 年获得南加州大学计算机科学硕士学位，1991 年获卡内基梅隆大学 (CMU) 计算机科学博士学位。在受聘于南加州大学之前，他曾在波士顿大学任教，是 Akamai 科技公司高级科学家，麻省理工学院 (MIT) 数学系客座教授，并在 IBM Almaden 研究中心、微软亚洲研究院等多家学术研究机构兼任研究员。此外，滕尚华教授还是 ACM Fellow。

2008 年，滕尚华教授因在算法的平滑分析领域的研究成果，获得理论计算机领域最高奖——哥德尔奖(Gödel Prize)。2009 年获得由美国数学学会和美国数学规划学会颁发的富尔克森奖(Fulkerson Prize)。他曾被西蒙斯基金会评为「世界上最具原创性的理论科学家」之一。