0
作者 | 莓酊、杏花
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/
2021-12-10
2021-12-09
2021-12-12
2021-12-12
雷峰網雷峰網(公眾號：雷峰網)
雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。
