0
作者 | 莓酊、杏花
FOCS由IEEE計算機學會的計算機數(shù)學基礎(chǔ)專委會提供資助，是計算機科學領(lǐng)域最頂級的國際會議，在整個理論計算機科學領(lǐng)域享有崇高的聲望，并被公認屬于難度最高的會議之一，與ACM計算理論年會（STOC）并稱理論計算機科學兩大頂會。
自1960年成立以來，F(xiàn)OCS歷年會議涵蓋的領(lǐng)域十分廣泛，包括算法和數(shù)據(jù)結(jié)構(gòu)、計算復雜性、密碼學、計算幾何、算法圖論與組合學、計算隨機性、計算博弈論和量子計算等。
會議致力于為計算機理論的基礎(chǔ)研究和新方法開創(chuàng)領(lǐng)域的研究者提供有一個交流和展示的平臺，而其崇高的聲望和極高的難度令很多科院工作者只能仰望。
深度學習大神、亞馬遜AI主任科學家李沐也只中過一篇。值得一提的是，95后學神、清華姚班畢業(yè)生、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/
論文介紹：
該論文的結(jié)果是朝著理解計算復雜性領(lǐng)域經(jīng)典百萬美元問題之一的答案邁出的一步，即 P vs. NP 問題。盡管這個數(shù)學問題已為人所知數(shù)十年，但仍未解決。這個問題是理解計算機解決問題能力的極限和計算性質(zhì)的核心。計算復雜性直接影響對密碼系統(tǒng)的信任，密碼系統(tǒng)依賴于不可能被破解的證據(jù)，并指導算法的所有研究，包括智能手機中的導航應用程序等日常人工制品。
P 與 NP 的問題在 1970 年代的冷戰(zhàn)期間正式化，主要歸因于當時在美國的史蒂夫·庫克和蘇聯(lián)的列昂尼德·萊文。它之所以重要，因為它將許多實際問題相互聯(lián)系起來。作者們研究了問題的代數(shù)變體。提供了有關(guān)計算某些多項式的難度的見解。Nutan Limaye 表示她們證明了使用某些算法無法有效計算某些多項式。
作者：
哥本哈根 IT 大學副教授，曾任孟買印度理工學院教授。
奧胡斯大學計算機科學發(fā)展學院教授。
Sébastien Tavenas
法國國家科學研究中心薩瓦勃朗峰大學數(shù)學實驗室教授。
麥琪獎（最佳學生論文）：來自麻省理工學院的《Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance》
論文鏈接：https://arxiv.org/abs/2106.02026
論文介紹：
n個節(jié)點樹的（未加權(quán)）樹編輯距離問題要求計算兩個具有節(jié)點標簽的有根樹之間的差異性度量。十多年前的當前最佳算法運行時間為
[Demaine、Mozes、Rossman 和 Weimann，ICALP 2007]。同一篇論文還表明，對于使用所謂的分解策略的任何算法來說， 是最佳運行時間，這幾乎是所有已知算法的基礎(chǔ)。這些算法也適用于加權(quán)樹編輯距離問題，在 APSP 猜想 [Bringmann、Gawrychowski、Mozes 和 Weimann，SODA 2018] 下無法在真正的亞立方時間內(nèi)解決該問題。作者通過展示
時間算法來解決未加權(quán)的樹編輯距離問題，從而打破三次障礙?？紤]一個等效的最大化問題并使用動態(tài)規(guī)劃方案，該方案涉及具有許多特殊屬性的矩陣。通過使用分解方案和幾種組合技術(shù)，作者將樹編輯距離減少到有界差分矩陣的最大加乘積，這可以在真正的亞立方時間內(nèi)解決 [Bringmann、Grandoni、Saha 和 Vassilevska Williams， FOCS 2016]。
作者：
毛嘯
麻省理工學院工程碩士在讀，本科獲得麻省理工學院數(shù)學與計算機雙學位。
第 29 屆國際信息學奧林匹克競賽（IOI 2017）銀牌。
今年的時間檢驗獎有7位“獲獎?wù)摺?，他們分別是：
FOCS 1991
作者：
Uriel Feige
以色列計算機科學家，任以色列雷霍沃特魏茨曼科學研究所計算機科學與應用數(shù)學系教授。
與 Amos Fiat 和 Adi Shamir 共同發(fā)明了 Feige-Fiat-Shamir 識別方案。
Shafrira Goldwasser
以色列裔美國計算機科學家，2012 年獲得圖靈獎。她是麻省理工學院電氣工程和計算機科學的 RSA 教授，數(shù)學科學教授（以色列魏茨曼科學研究所），Duality Technologies的聯(lián)合創(chuàng)始人和首席科學家，以及加州伯克利的 Simons 計算理論研究所所長。
László Lovász
匈牙利數(shù)學家和E?tv?s Loránd大學的名譽教授，在組合數(shù)學方面的工作成績斐然，他與阿維·威格德森 (Avi Wigderson) 共同獲得了 2021 年阿貝爾獎。2007年至2010年任國際數(shù)學聯(lián)盟主席，2014年至2020年任匈牙利科學院院長。
在圖論方面，Lovász 的顯著貢獻包括 Kneser 猜想和 Lovász 局部引理的證明，以及 Erd?s-Faber-Lovász 猜想的公式化。他也是 LLL 格約化算法的同名作者之一。
Shmuel Safra
以色列計算機科學家。以色列特拉維夫大學計算機科學教授。
Safra 的研究領(lǐng)域包括復雜性理論和自動機理論。他在自動機理論方面的工作研究了有限自動機在無限字符串上的確定性和互補性，特別是 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 的研究領(lǐng)域包括計算復雜性理論和量子計算。
他在 2001 年和 2005 年兩次獲得哥德爾獎，以表彰他在概率可檢驗證明和近似流數(shù)據(jù)中頻率矩的空間復雜度方面的工作。他在流媒體方面的工作也獲得了 2019 年巴黎卡內(nèi)拉基斯理論與實踐獎的認可。
《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
論文介紹：
該論文展示了如何使用δ源的輸出在多項式時間內(nèi)模擬 BPP 和近似算法。δ源是一個弱隨機源，它只對 R 位詢問一次，并且必須根據(jù)某種分布輸出一個 R 位串，該分布在任何特定串上的概率不超過
。此外，文章還應用了 MAX CLIQUE 的不可近似性。
作者：
David Zuckerman
美國理論計算機科學家，他的工作涉及計算中的隨機性。德克薩斯大學奧斯汀分校的計算機科學教授。
Zuckerman 的大部分工作都涉及計算中的隨機性，尤其是偽隨機性。他撰寫了 80 多篇論文，主題包括隨機性提取器、偽隨機生成器、編碼理論和密碼學。Zuckerman 以其在隨機性提取器方面的工作而聞名。2015 年，Zuckerman 和他的學生 Eshan Chattopadhyay 通過首次明確構(gòu)建雙源提取器，解決了該領(lǐng)域一個重要的開放問題。2016 年 ACM 計算理論研討會上獲得了最佳論文獎。
《Fast Approximation Algorithms for Fractional Packing and Covering Problems》
FOCS 1991
作者：
Serge A. Plotkin
斯坦福大學計算機科學系教授。Serge 已發(fā)表了一百多篇技術(shù)論文，并已獲得十四項專利。他曾擔任 IEEE 標準化委員會存儲安全工作組 P1619/P1619.1 的副主席，該委員會的任務(wù)是創(chuàng)建存儲加密標準，并且是 IEEE1619 標準的編輯。
David B. Shmoys
康奈爾大學運籌學與信息工程學院和計算機科學系的教授。主要研究方向是離散優(yōu)化問題算法的設(shè)計和分析。他的工作突出了線性規(guī)劃在 NP 難題的近似算法設(shè)計中的作用。以開創(chuàng)性研究為多個調(diào)度和聚類問題（包括 k 中心和 k 中值問題以及廣義分配問題）提供第一個常數(shù)因子性能保證而聞名。他為調(diào)度問題開發(fā)的多項式時間近似方案已在許多后續(xù)工作中得到應用。目前的研究包括計算生物學中的隨機優(yōu)化、計算可持續(xù)性和優(yōu)化技術(shù)。
éva Tardos
匈牙利數(shù)學家和康奈爾大學計算機科學的 Jacob Gould Schurman 教授。
Tardos 的研究興趣是算法。她的工作重點是設(shè)計和分析圖或網(wǎng)絡(luò)上組合優(yōu)化問題的有效方法。她在網(wǎng)絡(luò)流算法方面做了一些工作，例如網(wǎng)絡(luò)流、切割和聚類問題的近似算法。她最近的工作重點是算法博弈論和簡單拍賣。
《Universally Composable Security: A New Paradigm for Cryptographic Protocols》
FOCS 2001
論文鏈接：https://eprint.iacr.org/2000/067.pdf
論文介紹：
這篇論文提出了一個描述加密協(xié)議和分析其安全性的通用框架。該框架允許以統(tǒng)一和系統(tǒng)的方式指定幾乎任何加密任務(wù)的安全要求。此外，在該框架中，協(xié)議的安全性在稱為通用組合的通用組合操作下得到保護。所提出的框架及其安全保護組合操作允許從更簡單的構(gòu)建塊對復雜的密碼協(xié)議進行模塊化設(shè)計和分析。此外，在此框架內(nèi)，協(xié)議保證在任何上下文中保持其安全性，即使存在以對抗性控制方式并發(fā)運行的無限數(shù)量的任意協(xié)議會話也是如此。這是一個有用的保證，它允許在復雜和不可預測的環(huán)境（例如現(xiàn)代通信網(wǎng)絡(luò)）中加密協(xié)議的安全性。
作者：
Ran Canetti
波士頓大學計算機科學教授。Check Point 信息安全研究所 和可靠信息系統(tǒng)和網(wǎng)絡(luò)安全中心的主任。他還是《密碼學與信息與計算雜志》的副主編。他的主要研究領(lǐng)域涵蓋密碼學和信息安全，重點是密碼協(xié)議的設(shè)計、分析和使用。
《How to Go Beyond the Black-Box Simulation Barrier》
FOCS 2001
論文鏈接：https://www.boazbarak.org/Papers/nonbb.pdf
論文介紹：
模擬范式是密碼學的核心。模擬器是一種算法，它試圖在不知道這個誠實方的私人輸入的情況下模擬對手與誠實方的交互。幾乎所有已知的模擬器都將對手的算法用作黑盒。該論文展示了非黑盒模擬器的第一個結(jié)構(gòu)。使用這些新的非黑盒技術(shù)，研究人員獲得了幾個以前使用黑盒模擬器不可能獲得的結(jié)果。
具體來說，假設(shè)存在抗碰撞哈希函數(shù)，論文的作者為 NP 構(gòu)建了一個新的零知識參數(shù)系統(tǒng)，滿足以下屬性：
1）該系統(tǒng)具有恒定的輪數(shù)，穩(wěn)健性誤差可以忽略不計。
2）即使同時組合 n 次，它仍然是零知識，其中 n 是安全參數(shù)。已證明使用黑盒模擬器不可能同時獲得屬性 1 和 2。
3）它是一個 Arthur-Merlin（公共硬幣）協(xié)議。同時獲得屬性 1 和 3 也被證明是不可能用黑箱模擬器實現(xiàn)的。
4）它有一個在嚴格多項式時間內(nèi)運行的模擬器，而不是在預期的多項式時間內(nèi)。所有先前已知的滿足屬性 1 的零知識參數(shù)都使用了預期的多項式時間模擬器。這項工作表明，同時獲得屬性 1 和 4 也不可能用黑盒模擬器實現(xiàn)。
作者：
Boaz Barak
哈佛大學計算機科學系以色列裔美國教授。2013 年，他、羅伯特·J·戈德斯頓 (Robert J. Goldston) 和亞歷山大·格拉澤 (Alexander Glaser) 合作設(shè)計了一個“零知識”系統(tǒng)。通過將高能中子引導到被調(diào)查的彈頭中，并將穿過的分布與穿過已知彈頭的分布進行比較，檢查員可以確定被解除武裝的彈頭是真實的還是旨在逃避條約要求的詭計，而不會泄漏核秘密。由于這項工作，他被選為 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 個副本具有復雜度
；使用先前已知技術(shù)可證明的最佳下界是。研究人員還證明了等式函數(shù)的多個副本的某些布爾組合的類似下界。這些結(jié)果可以推廣到更廣泛的函數(shù)類。研究者們引入了一個新的信息復雜度概念，它與 SM 復雜度相關(guān)，并具有很好的直接和屬性。這個概念被用作證明上述結(jié)果的工具：它似乎非常強大，可能具有獨立的利益。
作者：
Amit Chakrabarti
達特茅斯學院計算機科學系的教授，2002 年獲得普林斯頓大學計算機科學學士學位和技術(shù)學士學位。1997 年獲得孟買印度理工學院計算機科學博士學位，并獲得印度總統(tǒng)金牌。Chakrabarti的研究涉及理論計算機科學的廣泛領(lǐng)域。具體興趣是（1）復雜性理論，尤其是通信復雜性和信息理論的應用，以及（2）算法，包括用于海量數(shù)據(jù)流的空間高效算法和用于優(yōu)化問題的近似技術(shù)。他的研究得到了美國國家科學基金會的多個獎項（包括 CAREER 獎）和達特茅斯學院的獎學金。
施堯耘
阿里云（阿里巴巴云）量子實驗室（AQL）的創(chuàng)始主任。施堯耘正在組建一個國際團隊，以實現(xiàn)量子信息技術(shù)的革命性潛力。1997年獲得北京大學學士學位。2001 年從普林斯頓大學獲得計算機科學博士學位。在加州理工學院量子信息研究所獲得博士后獎學金后，加入了密歇根大學安娜堡分校的計算機科學系。
Anthony Wirth
Anthony2005 年獲得普林斯頓普林斯頓大學博士學位。此后，一直是澳大利亞維多利亞州墨爾本墨爾本大學的教員。目前的研究興趣包括圖、字符串和近似算法、聚類、算法工程、自適應采樣和生物序列分析。
Andrew Chi-Chih Yao（姚期智）
計算機科學專家，2000年圖靈獎獲得者，美國國家科學院外籍院士、美國藝術(shù)與科學院外籍院士、中國科學院院士、臺灣中央研究院院士、香港科學院創(chuàng)院院士 ，清華大學交叉信息研究院院長，清華大學高等研究中心教授，香港中文大學博文講座教授 ，清華大學-麻省理工學院-香港中文大學理論計算機科學研究中心主任。研究方向包括計算理論及其在密碼學和量子計算中的應用，最先提出量子通信復雜性，提出分布式量子計算模式，后來成為分布式量子算法和量子通訊協(xié)議安全性的基礎(chǔ)。
《Efficient Fully Homomorphic Encryption from (Standard) LWE》
FOCS 2011
論文鏈接：https://eprint.iacr.org/2011/344.pdf
論文介紹：
該論文提出了一個完全同態(tài)的加密方案——完全基于（標準）有錯誤學習（LWE）假設(shè)。在 LWE 上應用已知結(jié)果，本論文方案的安全性基于任意格上“短向量問題”的最壞情況硬度。研究人員的構(gòu)造在兩個方面改進了以前的工作：
1）展示了“近似同態(tài)”的加密可以基于 LWE，使用一種新的重新線性化技術(shù)。相比之下，之前的所有方案都依賴于與各種環(huán)中的理想相關(guān)的復雜性假設(shè)。
2）偏離了之前使用的“擠壓范式”。研究人員引入了一種新的降維模數(shù)技術(shù)，它縮短了密文并降低了方案的解密復雜性，而無需引入額外的假設(shè)。
這篇論文的方案具有非常短的密文，因此研究者們使用它來構(gòu)建漸近高效的基于 LWE 的單服務(wù)器私有信息檢索 (PIR) 協(xié)議。研究人員協(xié)議的通信復雜度（在公鑰模型中）是 k · polylog(k) + log |DB| bits persingle-bit查詢（這里k是一個安全參數(shù)）。
作者：
Zvika Brakerski
魏茨曼科學研究所計算機科學與應用數(shù)學系的副教授，研究興趣為計算機科學基礎(chǔ)，目前主要從事密碼學和量子計算的研究。Zvika Brakerski 在魏茨曼科學研究所計算機科學與應用數(shù)學系2011年獲得了博士學位，隨后在斯坦福大學當了兩年 Simons 博士后研究員。
Vinod Vaikuntanathan
麻省理工學院電氣工程和計算機科學系的副教授、Duality Technologies 的首席密碼學家。他是大多數(shù)現(xiàn)代全同態(tài)加密系統(tǒng)和許多其他基于格的（后量子安全）密碼原語的共同發(fā)明者。獲得了 IBM Josef Raviv Fellowship、NSF Career Award、Sloan Faculty Fellowship、Microsoft Faculty Fellowship、DARPA Young Faculty Award 和 Harold E. Edgerton Faculty Award。獲得了印度理工學院馬德拉斯分校的技術(shù)學士學位，以及麻省理工學院的碩士和博士學位。
FOCS的前身為開關(guān)電路理論與邏輯設(shè)計研討會（Symposium on Switching Circuit Theory and Logical Design），1960年成立之時，該會議沒有單獨發(fā)表會議記錄，大多數(shù)論文都發(fā)表在1961年會議論文集后半部分。
在1966年舉行的第7次會議時，名稱改為開關(guān)和自動機理論研討會（Symposium on Switching and Automata Theory, SWAT）。
由于會議規(guī)模不斷擴大，1975年更名為現(xiàn)在的名稱。當時 Alvy Ray Smith 開啟了獨特的封面藝術(shù)，這一直 FOCS 會議記錄的一個特色，直到 2010 年 FOCS 結(jié)束印刷會議記錄的生產(chǎn)。風格化的 FOCS 狐貍標志則創(chuàng)建于第26屆會議。
本年度FOCS將于2022年2月7-10日在美國科羅拉多州丹佛市舉辦。
參考鏈接：
https://focs2021.cs.colorado.edu/
2021-12-10
2021-12-09
2021-12-12
2021-12-12
雷峰網(wǎng)(公眾號：雷峰網(wǎng))雷峰網(wǎng)
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
