您现在所在的位置是: 主页 > 新闻中心 >

理论计算机顶会 FOCS 2021 奖项揭晓!姚期智获时间检验奖MIT 毛

发布日期:2022-01-13 14:47   来源:未知   阅读:

  第 62 届 IEEE 计算机科学基础年度研讨会(FOCS 2021)各奖项揭晓!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  本年度 FOCS 将于 2022 年 2 月 7-10 日在美国科罗拉多州丹佛市举办。香港六宝典资料大全