理论计算机顶会FOCS 2021奖项揭晓！姚期智获时间检验奖，MIT毛啸获最佳学生论文奖

作者 | 莓酊、杏花

FOCS由IEEE计算机学会的计算机数学基础专委会提供资助，是计算机科学领域最顶级的国际会议，在整个理论计算机科学领域享有崇高的声望，并被公认属于难度最高的会议之一，与ACM计算理论年会（STOC）并称理论计算机科学两大顶会。

自1960年成立以来，FOCS历年会议涵盖的领域十分广泛，包括算法和数据结构、计算复杂性、密码学、计算几何、算法图论与组合学、计算随机性、计算博弈论和量子计算等。

会议致力于为计算机理论的基础研究和新方法开创领域的研究者提供有一个交流和展示的平台，而其崇高的声望和极高的难度令很多科院工作者只能仰望。

深度学习大神、亚马逊AI主任科学家李沐也只中过一篇。值得一提的是，95后学神、清华姚班毕业生、MIT博士生陈立杰则曾于2019年连中三元（其中两篇一作），并荣获最佳学生论文奖！今年的他也有两篇一作入选。

以下是FOCS 2021的各奖项情况：

最佳论文奖：来自印度理工学院、奥胡斯大学、Univ. Grenoble Alpes, Univ. Savoie Mont Blanc, CNRS, LAMA共同完成的《Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits》

论文地址：https://eccc.weizmann.ac.il/report/2021/081/

论文介绍：

该论文的结果是朝着理解计算复杂性领域经典百万美元问题之一的答案迈出的一步，即 P vs. NP 问题。尽管这个数学问题已为人所知数十年，但仍未解决。这个问题是理解计算机解决问题能力的极限和计算性质的核心。计算复杂性直接影响对密码系统的信任，密码系统依赖于不可能被破解的证据，并指导算法的所有研究，包括智能手机中的导航应用程序等日常人工制品。

P 与 NP 的问题在 1970 年代的冷战期间正式化，主要归因于当时在美国的史蒂夫·库克和苏联的列昂尼德·莱文。它之所以重要，因为它将许多实际问题相互联系起来。作者们研究了问题的代数变体。提供了有关计算某些多项式的难度的见解。Nutan Limaye 表示她们证明了使用某些算法无法有效计算某些多项式。

作者：

哥本哈根 IT 大学副教授，曾任孟买印度理工学院教授。

奥胡斯大学计算机科学发展学院教授。

Sébastien Tavenas

法国国家科学研究中心萨瓦勃朗峰大学数学实验室教授。

麦琪奖（最佳学生论文）：来自麻省理工学院的《Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance》

论文链接：https://arxiv.org/abs/2106.02026

论文介绍：

n个节点树的（未加权）树编辑距离问题要求计算两个具有节点标签的有根树之间的差异性度量。十多年前的当前最佳算法运行时间为 [Demaine、Mozes、Rossman 和 Weimann，ICALP 2007]。同一篇论文还表明，对于使用所谓的分解策略的任何算法来说， 是最佳运行时间，这几乎是所有已知算法的基础。这些算法也适用于加权树编辑距离问题，在 APSP 猜想 [Bringmann、Gawrychowski、Mozes 和 Weimann，SODA 2018] 下无法在真正的亚立方时间内解决该问题。作者通过展示 时间算法来解决未加权的树编辑距离问题，从而打破三次障碍。考虑一个等效的最大化问题并使用动态规划方案，该方案涉及具有许多特殊属性的矩阵。通过使用分解方案和几种组合技术，作者将树编辑距离减少到有界差分矩阵的最大加乘积，这可以在真正的亚立方时间内解决 [Bringmann、Grandoni、Saha 和 Vassilevska Williams， FOCS 2016]。

作者：

毛啸

麻省理工学院工程硕士在读，本科获得麻省理工学院数学与计算机双学位。

第 29 届国际信息学奥林匹克竞赛（IOI 2017）银牌。

今年的时间检验奖有7位“获奖者”，他们分别是：

FOCS 1991

作者：

Uriel Feige

以色列计算机科学家，任以色列雷霍沃特魏茨曼科学研究所计算机科学与应用数学系教授。

与 Amos Fiat 和 Adi Shamir 共同发明了 Feige-Fiat-Shamir 识别方案。

Shafrira Goldwasser

以色列裔美国计算机科学家，2012 年获得图灵奖。她是麻省理工学院电气工程和计算机科学的 RSA 教授，数学科学教授（以色列魏茨曼科学研究所），Duality Technologies的联合创始人和首席科学家，以及加州伯克利的 Simons 计算理论研究所所长。

László Lovász

匈牙利数学家和Eötvös Loránd大学的名誉教授，在组合数学方面的工作成绩斐然，他与阿维·威格德森 (Avi Wigderson) 共同获得了 2021 年阿贝尔奖。2007年至2010年任国际数学联盟主席，2014年至2020年任匈牙利科学院院长。

在图论方面，Lovász 的显着贡献包括 Kneser 猜想和 Lovász 局部引理的证明，以及 Erdős-Faber-Lovász 猜想的公式化。他也是 LLL 格约化算法的同名作者之一。

Shmuel Safra

以色列计算机科学家。以色列特拉维夫大学计算机科学教授。

Safra 的研究领域包括复杂性理论和自动机理论。他在自动机理论方面的工作研究了有限自动机在无限字符串上的确定性和互补性，特别是 Büchi 自动机、Street 自动机和 Rabin 自动机的翻译复杂性。

2001 年，Safra 因其论文“Interactive Proofs and the Hardness of Approximating Cliques”和“Probabilistic Checking of Proofs: A New Characterization of NP”获得理论计算机科学哥德尔奖。

Mario Szegedy

匈牙利裔美国计算机科学家，罗格斯大学计算机科学教授。他获得了博士学位。1989 年获得芝加哥大学计算机科学博士学位。Szegedy 的研究领域包括计算复杂性理论和量子计算。

他在 2001 年和 2005 年两次获得哥德尔奖，以表彰他在概率可检验证明和近似流数据中频率矩的空间复杂度方面的工作。他在流媒体方面的工作也获得了 2019 年巴黎卡内拉基斯理论与实践奖的认可。

《Simulating BPP Using a General Weak Random Source》

FOCS 1991

论文链接：https://www.cs.utexas.edu/~diz/Sub%20Websites/Research/Simulating_bpp_using_a_general_weak_random_sources.pdf

论文介绍：

该论文展示了如何使用δ源的输出在多项式时间内模拟 BPP 和近似算法。δ源是一个弱随机源，它只对 R 位询问一次，并且必须根据某种分布输出一个 R 位串，该分布在任何特定串上的概率不超过。此外，文章还应用了 MAX CLIQUE 的不可近似性。

作者：

David Zuckerman

美国理论计算机科学家，他的工作涉及计算中的随机性。德克萨斯大学奥斯汀分校的计算机科学教授。

Zuckerman 的大部分工作都涉及计算中的随机性，尤其是伪随机性。他撰写了 80 多篇论文，主题包括随机性提取器、伪随机生成器、编码理论和密码学。Zuckerman 以其在随机性提取器方面的工作而闻名。2015 年，Zuckerman 和他的学生 Eshan Chattopadhyay 通过首次明确构建双源提取器，解决了该领域一个重要的开放问题。2016 年 ACM 计算理论研讨会上获得了最佳论文奖。

《Fast Approximation Algorithms for Fractional Packing and Covering Problems》

FOCS 1991

作者：

Serge A. Plotkin

斯坦福大学计算机科学系教授。Serge 已发表了一百多篇技术论文，并已获得十四项专利。他曾担任 IEEE 标准化委员会存储安全工作组 P1619/P1619.1 的副主席，该委员会的任务是创建存储加密标准，并且是 IEEE1619 标准的编辑。

David B. Shmoys

康奈尔大学运筹学与信息工程学院和计算机科学系的教授。主要研究方向是离散优化问题算法的设计和分析。他的工作突出了线性规划在 NP 难题的近似算法设计中的作用。以开创性研究为多个调度和聚类问题（包括 k 中心和 k 中值问题以及广义分配问题）提供第一个常数因子性能保证而闻名。他为调度问题开发的多项式时间近似方案已在许多后续工作中得到应用。目前的研究包括计算生物学中的随机优化、计算可持续性和优化技术。

Éva Tardos

匈牙利数学家和康奈尔大学计算机科学的 Jacob Gould Schurman 教授。

Tardos 的研究兴趣是算法。她的工作重点是设计和分析图或网络上组合优化问题的有效方法。她在网络流算法方面做了一些工作，例如网络流、切割和聚类问题的近似算法。她最近的工作重点是算法博弈论和简单拍卖。

《Universally Composable Security: A New Paradigm for Cryptographic Protocols》

FOCS 2001

论文链接：https://eprint.iacr.org/2000/067.pdf

论文介绍：

这篇论文提出了一个描述加密协议和分析其安全性的通用框架。该框架允许以统一和系统的方式指定几乎任何加密任务的安全要求。此外，在该框架中，协议的安全性在称为通用组合的通用组合操作下得到保护。所提出的框架及其安全保护组合操作允许从更简单的构建块对复杂的密码协议进行模块化设计和分析。此外，在此框架内，协议保证在任何上下文中保持其安全性，即使存在以对抗性控制方式并发运行的无限数量的任意协议会话也是如此。这是一个有用的保证，它允许在复杂和不可预测的环境（例如现代通信网络）中加密协议的安全性。

作者：

Ran Canetti

波士顿大学计算机科学教授。Check Point 信息安全研究所 和可靠信息系统和网络安全中心的主任。他还是《密码学与信息与计算杂志》的副主编。他的主要研究领域涵盖密码学和信息安全，重点是密码协议的设计、分析和使用。

《How to Go Beyond the Black-Box Simulation Barrier》

FOCS 2001

论文链接：https://www.boazbarak.org/Papers/nonbb.pdf

论文介绍：

模拟范式是密码学的核心。模拟器是一种算法，它试图在不知道这个诚实方的私人输入的情况下模拟对手与诚实方的交互。几乎所有已知的模拟器都将对手的算法用作黑盒。该论文展示了非黑盒模拟器的第一个结构。使用这些新的非黑盒技术，研究人员获得了几个以前使用黑盒模拟器不可能获得的结果。

具体来说，假设存在抗碰撞哈希函数，论文的作者为 NP 构建了一个新的零知识参数系统，满足以下属性：

1）该系统具有恒定的轮数，稳健性误差可以忽略不计。

2）即使同时组合 n 次，它仍然是零知识，其中 n 是安全参数。已证明使用黑盒模拟器不可能同时获得属性 1 和 2。

3）它是一个 Arthur-Merlin（公共硬币）协议。同时获得属性 1 和 3 也被证明是不可能用黑箱模拟器实现的。

4）它有一个在严格多项式时间内运行的模拟器，而不是在预期的多项式时间内。所有先前已知的满足属性 1 的零知识参数都使用了预期的多项式时间模拟器。这项工作表明，同时获得属性 1 和 4 也不可能用黑盒模拟器实现。

作者：

Boaz Barak

哈佛大学计算机科学系以色列裔美国教授。2013 年，他、罗伯特·J·戈德斯顿 (Robert J. Goldston) 和亚历山大·格拉泽 (Alexander Glaser) 合作设计了一个“零知识”系统。通过将高能中子引导到被调查的弹头中，并将穿过的分布与穿过已知弹头的分布进行比较，检查员可以确定被解除武装的弹头是真实的还是旨在逃避条约要求的诡计，而不会泄漏核秘密。由于这项工作，他被选为 2014 年“外交政策”全球 100 位思想家问题。他与 Mark Braverman、Xi Chen 和 Anup Rao 共同凭借论文“How to Compress Interactive Communication”获得 2016 年 SIAM 杰出论文奖。

《Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity》

FOCS 2001

论文链接：https://www.cs.dartmouth.edu/~ac/Pubs/focs01-infocomplex.pdf

论文介绍：

给定 m 个相同问题的副本，解决这 m 个问题是否需要 m 倍的资源？这是直和问题，这是许多计算模型中研究过的基本问题。这篇论文在引入的同步消息（SM）通信模型中研究了这个问题。众所周知，n 位字符串的相等问题具有 SM 复杂度。研究人员证明解决问题的 m 个副本具有复杂度；使用先前已知技术可证明的最佳下界是。研究人员还证明了等式函数的多个副本的某些布尔组合的类似下界。这些结果可以推广到更广泛的函数类。研究者们引入了一个新的信息复杂度概念，它与 SM 复杂度相关，并具有很好的直接和属性。这个概念被用作证明上述结果的工具：它似乎非常强大，可能具有独立的利益。

作者：

Amit Chakrabarti

达特茅斯学院计算机科学系的教授，2002 年获得普林斯顿大学计算机科学学士学位和技术学士学位。1997 年获得孟买印度理工学院计算机科学博士学位，并获得印度总统金牌。Chakrabarti的研究涉及理论计算机科学的广泛领域。具体兴趣是（1）复杂性理论，尤其是通信复杂性和信息理论的应用，以及（2）算法，包括用于海量数据流的空间高效算法和用于优化问题的近似技术。他的研究得到了美国国家科学基金会的多个奖项（包括 CAREER 奖）和达特茅斯学院的奖学金。

施尧耘

阿里云（阿里巴巴云）量子实验室（AQL）的创始主任。施尧耘正在组建一个国际团队，以实现量子信息技术的革命性潜力。1997年获得北京大学学士学位。2001 年从普林斯顿大学获得计算机科学博士学位。在加州理工学院量子信息研究所获得博士后奖学金后，加入了密歇根大学安娜堡分校的计算机科学系。

Anthony Wirth

Anthony2005 年获得普林斯顿普林斯顿大学博士学位。此后，一直是澳大利亚维多利亚州墨尔本墨尔本大学的教员。目前的研究兴趣包括图、字符串和近似算法、聚类、算法工程、自适应采样和生物序列分析。

Andrew Chi-Chih Yao（姚期智）

计算机科学专家，2000年图灵奖获得者，美国国家科学院外籍院士、美国艺术与科学院外籍院士、中国科学院院士、台湾中央研究院院士、香港科学院创院院士 ，清华大学交叉信息研究院院长，清华大学高等研究中心教授，香港中文大学博文讲座教授 ，清华大学-麻省理工学院-香港中文大学理论计算机科学研究中心主任。研究方向包括计算理论及其在密码学和量子计算中的应用，最先提出量子通信复杂性，提出分布式量子计算模式，后来成为分布式量子算法和量子通讯协议安全性的基础。

《Efficient Fully Homomorphic Encryption from (Standard) LWE》

FOCS 2011

论文链接：https://eprint.iacr.org/2011/344.pdf

论文介绍：

该论文提出了一个完全同态的加密方案——完全基于（标准）有错误学习（LWE）假设。在 LWE 上应用已知结果，本论文方案的安全性基于任意格上“短向量问题”的最坏情况硬度。研究人员的构造在两个方面改进了以前的工作：

1）展示了“近似同态”的加密可以基于 LWE，使用一种新的重新线性化技术。相比之下，之前的所有方案都依赖于与各种环中的理想相关的复杂性假设。

2）偏离了之前使用的“挤压范式”。研究人员引入了一种新的降维模数技术，它缩短了密文并降低了方案的解密复杂性，而无需引入额外的假设。

这篇论文的方案具有非常短的密文，因此研究者们使用它来构建渐近高效的基于 LWE 的单服务器私有信息检索 (PIR) 协议。研究人员协议的通信复杂度（在公钥模型中）是 k · polylog(k) + log |DB| bits persingle-bit查询（这里k是一个安全参数）。

作者：

Zvika Brakerski

魏茨曼科学研究所计算机科学与应用数学系的副教授，研究兴趣为计算机科学基础，目前主要从事密码学和量子计算的研究。Zvika Brakerski 在魏茨曼科学研究所计算机科学与应用数学系2011年获得了博士学位，随后在斯坦福大学当了两年 Simons 博士后研究员。

Vinod Vaikuntanathan

麻省理工学院电气工程和计算机科学系的副教授、Duality Technologies 的首席密码学家。他是大多数现代全同态加密系统和许多其他基于格的（后量子安全）密码原语的共同发明者。获得了 IBM Josef Raviv Fellowship、NSF Career Award、Sloan Faculty Fellowship、Microsoft Faculty Fellowship、DARPA Young Faculty Award 和 Harold E. Edgerton Faculty Award。获得了印度理工学院马德拉斯分校的技术学士学位，以及麻省理工学院的硕士和博士学位。

FOCS的前身为开关电路理论与逻辑设计研讨会（Symposium on Switching Circuit Theory and Logical Design），1960年成立之时，该会议没有单独发表会议记录，大多数论文都发表在1961年会议论文集后半部分。

在1966年举行的第7次会议时，名称改为开关和自动机理论研讨会（Symposium on Switching and Automata Theory, SWAT）。

由于会议规模不断扩大，1975年更名为现在的名称。当时 Alvy Ray Smith 开启了独特的封面艺术，这一直 FOCS 会议记录的一个特色，直到 2010 年 FOCS 结束印刷会议记录的生产。风格化的 FOCS 狐狸标志则创建于第26届会议。

本年度FOCS将于2022年2月7-10日在美国科罗拉多州丹佛市举办。

参考链接：

https://focs2021.cs.colorado.edu/

GAIR 2021大会首日：18位Fellow的40年AI岁月，一场技术前沿的传承与激辩

2021-12-10

致敬传奇：中国并行处理四十年，他们从无人区探索走到计算的黄金时代 | GAIR 2021

2021-12-09

时间的力量——1991 人工智能大辩论 30 周年纪念：主义不再，共融互生｜GAIR 2021

2021-12-12

未来已来，元宇宙比你想象中来得更早丨GAIR 2021

2021-12-12

雷峰网(公众号：雷峰网)雷峰网

雷峰网原创文章，未经授权禁止转载。详情见转载须知。