Auto Byte

专注未来出行及智能汽车科技

微信扫一扫获取更多资讯

Science AI

关注人工智能与其他前沿技术、基础学科的交叉研究与融合发展

微信扫一扫获取更多资讯

小舟、张倩编辑

计算机理论顶会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(利物浦大学)

  • 论文链接:https://arxiv.org/pdf/2011.01929.pdf

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

论文 3:Indistinguishability Obfuscation from Well-Founded Assumptions

  • 作者:Aayush Jain(加州大学洛杉矶分校)、Huijia Lin(华盛顿大学)、Amit Sahai(加州大学洛杉矶分校)

  • 论文链接:https://eprint.iacr.org/2020/1003.pdf

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(麻省理工学院)

  • 论文链接:https://arxiv.org/abs/2006.14009


该研究探究了在各种设置下中向量的差异最小化,在多个维度上分析了一个新的简单随机过程。根据研究结果的推论,研究者推算出由 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

  • 论文链接:https://dl.acm.org/doi/10.1145/62212.62213


  • 论文 2:Multiparty unconditionally secure protocols(STOC 1988)

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

  • 论文链接:https://dl.acm.org/doi/10.1145/62212.62214


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

  • 作者:Tal Rabin、Michael Ben-Or

  • 论文链接:https://dl.acm.org/doi/10.1145/73007.73014


  • 论文 4:A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries(STOC 2001)

  • 作者:Mark Jerrum、Alistair Sinclair、Eric Vigoda

  • 论文链接:https://www.cc.gatech.edu/~vigoda/Permanent.pdf


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

  • 作者:Daniel A. Spielman、Shang-Hua Teng

  • 论文链接:https://arxiv.org/pdf/cs/0111050.pdf


  • 论文 6:Approximate distance oracles

  • 作者:Mikkel Thorup、Uri Zwick

  • 论文链接:http://www.cs.jhu.edu/~baruch/teaching/600.427/Papers/oracle-STOC-try.pdf


  • 论文 7:The computational complexity of linear optics

  • 作者:Scott Aaronson、Alex Arkhipov

  • 论文链接:https://arxiv.org/pdf/1011.3245.pdf


论文 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)。他曾被西蒙斯基金会评为「世界上最具原创性的理论科学家」之一。

参考链接:

https://www.sigact.org/articles/prizes.html


产业基础理论论文奖项STOC
相关数据
微软亚洲研究院机构

微软亚洲研究院于1998年在北京成立,是微软公司在亚太地区设立的基础及应用研究机构,也是微软在美国本土以外规模最大的一个研究院。微软亚洲研究院从事自然用户界面、智能多媒体、大数据与知识挖掘、人工智能、云和边缘计算、计算机科学基础等领域的研究,致力于推动计算机科学前沿发展,着眼下一代革命性技术的创新,助力微软实现长远发展战略。

www.msra.cn
IBM机构

是美国一家跨国科技公司及咨询公司,总部位于纽约州阿蒙克市。IBM主要客户是政府和企业。IBM生产并销售计算机硬件及软件,并且为系统架构和网络托管提供咨询服务。截止2013年,IBM已在全球拥有12个研究实验室和大量的软件开发基地。IBM虽然是一家商业公司,但在材料、化学、物理等科学领域却也有很高的成就,利用这些学术研究为基础,发明很多产品。比较有名的IBM发明的产品包括硬盘、自动柜员机、通用产品代码、SQL、关系数据库管理系统、DRAM及沃森。

https://www.ibm.com/us-en/
相关技术
深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

局部搜索技术

在计算机科学中,局部搜索是解决最优化问题的一种元启发式算法。局部搜索从一个初始解出发,然后搜索解的邻域,如有更优的解则移动至该解并继续执行搜索,否则返回当前解。局部搜索的优点是简单、灵活及易于实现,缺点是容易陷入局部最优且解的质量与初始解和邻域的结构密切相关。常见的改进方法有模拟退火、禁忌搜索等。

人工智能技术

在学术研究领域,人工智能通常指能够感知周围环境并采取行动以实现最优的可能结果的智能体(intelligent agent)

规划技术

人工智能领域的「规划」通常是指智能体执行的任务/动作的自动规划和调度,其目的是进行资源的优化。常见的规划方法包括经典规划(Classical Planning)、分层任务网络(HTN)和 logistics 规划。

随机过程技术

在概率论概念中,随机过程是随机变量的集合。若一随机系统的样本点是随机函数,则称此函数为样本函数,这一随机系统全部样本函数的集合是一个随机过程。实际应用中,样本函数的一般定义在时间域或者空间域。随机过程的实例如股票和汇率的波动、语音信号、视频信号、体温的变化,反对法随机运动如布朗运动、随机徘徊等等。

线性规划技术

在数学中,线性规划(Linear Programming,简称LP)特指目标函数和约束条件皆为线性的最优化问题。

推荐系统技术

推荐系统(RS)主要是指应用协同智能(collaborative intelligence)做推荐的技术。推荐系统的两大主流类型是基于内容的推荐系统和协同过滤(Collaborative Filtering)。另外还有基于知识的推荐系统(包括基于本体和基于案例的推荐系统)是一类特殊的推荐系统,这类系统更加注重知识表征和推理。

数据挖掘技术

数据挖掘(英语:data mining)是一个跨学科的计算机科学分支 它是用人工智能、机器学习、统计学和数据库的交叉方法在相對較大型的数据集中发现模式的计算过程。 数据挖掘过程的总体目标是从一个数据集中提取信息,并将其转换成可理解的结构,以进一步使用。

梯度下降技术

梯度下降是用于查找函数最小值的一阶迭代优化算法。 要使用梯度下降找到函数的局部最小值,可以采用与当前点的函数梯度(或近似梯度)的负值成比例的步骤。 如果采取的步骤与梯度的正值成比例,则接近该函数的局部最大值,被称为梯度上升。

博弈论技术

博弈论,又译为对策论,或者赛局理论,应用数学的一个分支,1944年冯·诺伊曼与奥斯卡·摩根斯特恩合著《博弈论与经济行为》,标志着现代系统博弈理论的的初步形成,因此他被称为“博弈论之父”。博弈论被认为是20世纪经济学最伟大的成果之一

旅行推销员问题技术

旅行推销员问题是这样一个问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题,在运筹学和理论计算机科学中非常重要。 TSP是旅行购买者问题与车辆路径问题的一种特殊情况。 在计算复杂性理论中,TSP的做决定版本属于NP完全问题。

量子计算技术

量子计算结合了过去半个世纪以来两个最大的技术变革:信息技术和量子力学。如果我们使用量子力学的规则替换二进制逻辑来计算,某些难以攻克的计算任务将得到解决。追求通用量子计算机的一个重要目标是确定当前经典计算机无法承载的最小复杂度的计算任务。该交叉点被称为「量子霸权」边界,是在通向更强大和有用的计算技术的关键一步。

暂无评论
暂无评论~