米兰·(milan)中国官方网站-理论计算机顶会FOCS 2021奖项揭晓！姚期智获时间检验奖，MIT毛啸获最佳学生论文奖
作者| 莓酊、杏花
编纂 | 青暮第62届IEEE计较机科学基础年度钻研会（FOCS 2021）各奖项揭晓！FOCS由IEEE计较机学会的计较机数学基础专委会提供资助，是计较机科学范畴最顶级的国际集会，于整个理论计较机科学范畴享有高尚的声望，并被公认属在难度最高的集会之一，与ACM计较理论年会（STOC）并称理论计较机科学两年夜顶会。
自1960年景立以来，FOCS积年集会涵盖的范畴十分广泛，包括算法及数据布局、计较繁杂性、暗码学、计较几何、算法图论与组合学、计较随机性、计较博弈论及量子计较等。
集会致力在为计较机理论的基础研究及新要领创始范畴的研究者提供有一个交流及展示的平台，而其高尚的声望及极高的难度令许多科院事情者只能仰望。
深度进修年夜神、亚马逊AI主任科学家李沐也只中过一篇。值患上一提的是，95后学神、清华姚班卒业生、MIT博士生陈立杰则曾经在2019年连中三元（此中两篇一作），并荣获最好学生论文奖！本年的他也有两篇一作入选。
如下是FOCS 2021的各奖项环境：
1最好论文奖最好论文奖：来自印度理工学院、奥胡斯年夜学、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 暗示她们证实了利用某些算法没法有用计较某些多项式。
作者：
Nutan Limaye
哥本哈根 IT 年夜学副传授，曾经任孟买印度理工学院传授。
Srikanth Srinivasan
奥胡斯年夜学计较机科学成长学院传授。
Sébastien Tavenas
法国国度科学研究中央萨瓦勃朗峰年夜学数学试验室传授。
2最好学生论文奖麦琪奖（最好学生论文）：来自麻省理工学院的《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）银牌。
3时间查验奖本年的时间查验奖有7位“获奖者”，他们别离是：
1.Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy:《Approximating Clique is Almost NP-Complete》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 年巴黎卡内拉基斯理论与实践奖的承认。
2.David Zuckerman:《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 计较理论钻研会上得到了最好论文奖。
3.Serge A. Plotkin, David B. Shmoys, Éva Tardos:《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 的研究兴致是算法。她的事情重点是设计及阐发图或者收集上组合优化问题的有用要领。她于收集流算法方面做了一些事情，例如收集流、切割及聚类问题的类似算法。她近来的事情重点是算法博弈论及简朴拍卖。
4.Ran Canetti:《Universally Composable Security: A New Paradigm for Cryptographic Protocols》
FOCS 2001
论文链接：https://eprint.iacr.org/2000/067.pdf
论文先容：
这篇论文提出了一个描写加密和谈及阐发其安全性的通用框架。该框架答应以同一及体系的方式指定险些任何加密使命的安全要求。此外，于该框架中，和谈的安全性于称为通用组合的通用组合操作下获得掩护。所提出的框架和其安全掩护组合操作答应从更简朴的构建块对于繁杂的暗码和谈举行模块化设计及阐发。此外，于此框架内，和谈包管于任何上下文中连结其安全性，纵然存于以匹敌性节制方式并发运行的无穷数目的肆意和谈会话也是云云。这是一个有效的包管，它答应于繁杂及不成猜测的情况（例如现代通讯收集）中加密和谈的安全性。
作者：
Ran Canetti
波士顿年夜学计较机科学传授。Check Point 信息安全研究所 及靠得住信息体系及收集安全中央的主任。他还有是《暗码学与信息与计较杂志》的副主编。他的重要研究范畴涵盖暗码学及信息安全，重点是暗码和谈的设计、阐发及利用。
5.Boaz Barak:《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 Co妹妹unication”得到 2016 年 SIAM 卓异论文奖。
6.Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Chi-Chih Yao:《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 年得到普林斯顿普林斯顿年夜学博士学位。今后，一直是Australia维多利亚州墨尔本墨尔本年夜学的老师。今朝的研究兴致包括图、字符串及类似算法、聚类、算法工程、自顺应采样及生物序列阐发。
Andrew Chi-Chih Yao（姚期智）
计较机科学专家，2000年图灵奖得到者，美国国度科学院外籍院士、美国艺术与科学院外籍院士、中国科学院院士、中国台湾中心研究院院士、中国香港科学院创院院士 ，清华年夜学交织信息研究院院长，清华年夜学高档研究中央传授，中国香港中文年夜学博文讲座传授 ，清华年夜学-麻省理工学院-中国香港中文年夜学理论计较机科学研究中央主任。研究标的目的包括计较理论和其于暗码学及量子计较中的运用，开始提出量子通讯繁杂性，提出漫衍式量子计较模式，厥后成为漫衍式量子算法及量子通信和谈安全性的基础。
7.Zvika Brakerski, Vinod Vaikuntanathan:《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。得到了印度理工学院马德拉斯分校的技能学士学位，以和麻省理工学院的硕士及博士学位。
5关在FOCSFOCS的前身为开关电路理论与逻辑设计钻研会（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
雷峰网雷峰网(公家号：雷峰网)
雷峰网原创文章，未经授权禁止转载。详情见转载须知。
-米兰·(milan)中国官方网站
