机器之心 道
近日，全球计算机理论顶会 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 的最佳论文奖，分别是：
旅行推销员问题（TSP）是组合优化中最基本的问题之一。在这篇论文中，对于某个
，研究者为度量空间下的旅行推销员问题（metric TSP）给出了一个随机
逼近算法。
在这篇论文中，研究者探讨了在有界凸多边形域上能用梯度下降法求解的搜索问题，并证明了这类连续局部搜索（CLS）问题等于两个已知类的交集：PPAD 和 PLS。
iO（Indistinguishability Obfuscation，不可区分混淆）是密码学中黑科技一样的存在，它不仅可以隐藏数据集合，还可以隐藏计算机程序的内部工作机制，创造出强大的加密工具。但这种力量的强大让人们怀疑 iO 是否真的存在。
在这篇最佳论文中，研究者首次展示了如何仅使用安全假设来构建 iO。它从理论角度提供了一种即时构建多个加密工具的方式，而这在之前是不可能的。例如，它允许创建加密和加密。以色列理工学院教授 Yuval Ishai 曾表示：（详见：《不可区分混淆被实现，计算机科学家摘得这颗密码学）
最佳学生论文奖
STOC Danny Lewin 最佳学生论文奖是为了纪念著名数学家和企业家 Danny Lewin 设立的，他曾参与创立互联 公司 Akamai Technologies。今年共有两篇论文获得 Danny Lewin 最佳学生论文奖。
该研究探究了在各种设置下
中向量的差异最小化，在多个维度上分析了一个新的简单随机过程。根据研究结果的推论，研究者推算出由 Bansal 等人提出的在线向量平衡中几个问题的对数因子的严格边界，并提出了 Komlós 猜想的对数边界的线性时间算法。
该研究证明对于任意不同的 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 年三个类别，分别是：
在这篇论文中，滕教授和 Spielman 使用平滑分析的概念为了解算法性能给出了更实际的理解方法，例如度量其运行时间。这个概念有助于解释一个现象：为什么有些算法在实践中比理论上更有效？该研究发现，许多算法，尤其是广泛使用的线性规划单纯形算法，只要输入中有噪声就可以工作，而现实世界的数据中通常存在噪声。该研究的发现已应用于无数实用算法，涉及互联 通信、深度学习、数据挖掘、差分隐私、博弈论和个性化推荐系统等多个领域。
滕尚华于 1985 年毕业于上海交通大学，获得电气工程和计算机科学双学士学位，1988 年获得南加州大学计算机科学硕士学位，1991 年获卡内基梅隆大学 (CMU) 计算机科学博士学位。在受聘于南加州大学之前，他曾在波士顿大学任教，是 Akamai 科技公司高级科学家，麻省理工学院 (MIT) 数学系客座教授，并在 IBM Almaden 研究中心、微软亚洲研究院等多家学术研究机构兼任研究员。此外，滕尚华教授还是 ACM Fellow。
2008 年，滕尚华教授因在算法的平滑分析领域的研究成果，获得理论计算机领域最高奖——哥德尔奖(G?del Prize)。2009 年获得由美国数学学会和美国数学规划学会颁发的富尔克森奖(Fulkerson Prize)。他曾被西蒙斯基金会评为之一。
参考链接：
https://www.sigact.org/articles/prizes.html
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！