計算機理論頂會STOC 2021獎項出爐，滕尚華等華人學者獲獎

近日，全球計算機理論頂會 ACM STOC 公佈了今年的最佳論文獎、最佳學生論文獎、時間檢驗獎等獎項。南加州大學電腦科學與數學系教授滕尚華等多位華人學者獲獎。

作為計算機理論領域的全球頂級學術會議，ACM 計算理論年會（ACM Symposium on Theory of Computing，STOC）始於 1969 年，今年已經舉辦了 53 屆。

STOC 在整個電腦科學領域享有崇高的聲望，屬於公認難度最高的會議之一。與人工智慧不同，計算機理論領域被認為是國內學界與全球頂級水平相距較大的方向，在 STOC 大會中，2000-2017 年大陸研究機構平均每年發表的論文數量僅為 0.89 篇。

該會議由 ACM SIGACT (Special Interest Group in Algorithms and Computation Theory) 主辦，歷年會議涵蓋的領域十分廣泛，包括演算法和資料結構、計算複雜性、密碼學、計算幾何、組合學、隨機與去隨機化、演算法博弈論和量子計算等。受疫情影響，STOC 2021 於 2021 年 6 月 21-25 日線上舉行。

在 STOC 2021 上，南加州大學電腦科學與數學系教授、哥德爾獎得主滕尚華的論文摘得時間檢驗獎。此外，來自華盛頓大學的 Huijia Lin 參與的論文《Indistinguishability Obfuscation from Well-Founded Assumptions》獲最佳論文獎，他們研究的 iO 問題被譽為密碼學「皇冠上的明珠」。

以下是 STOC 2021 的具體獲獎情況。

最佳論文獎

今年，共有三篇論文摘得 STOC 的最佳論文獎，分別是：

論文 1：A (Slightly) Improved Approximation Algorithm for Metric TSP

• 作者：Anna R. Karlin（華盛頓大學）、Nathan Klein（華盛頓大學）、Shayan Oveis Gharan（華盛頓大學）

• 論文連結：https://arxiv.org/pdf/2007.01409.pdf

旅行推銷員問題（TSP）是組合優化中最基本的問題之一。在這篇論文中，對於某個

，研究者為度量空間下的旅行推銷員問題（metric TSP）給出了一個隨機

逼近演算法。

論文 2：The Complexity of Gradient Descent: CLS = PPAD ∩ PLS

• 作者：John Fearnley（利物浦大學）、Paul W. Goldberg（牛津大學）、Alexandros Hollender（牛津大學）、Rahul Savani（利物浦大學）

• 論文連結：https://arxiv.org/pdf/2011.01929.pdf

在這篇論文中，研究者探討了在有界凸多邊形域上能用梯度下降法求解的搜尋問題，並證明了這類連續局部搜尋（CLS）問題等於兩個已知類的交集：PPAD 和 PLS。

論文 3：Indistinguishability Obfuscation from Well-Founded Assumptions

• 作者：Aayush Jain（加州大學洛杉磯分校）、Huijia Lin（華盛頓大學）、Amit Sahai（加州大學洛杉磯分校）

• 論文連結：https://eprint.iacr.org/2020/1003.pdf

iO（Indistinguishability Obfuscation，不可區分混淆）是密碼學中黑科技一樣的存在，它不僅可以隱藏資料集合，還可以隱藏計算機程式的內部工作機制，創造出強大的加密工具。但這種力量的強大讓人們懷疑 iO 是否真的存在。

在這篇最佳論文中，研究者首次展示瞭如何僅使用「標準」安全假設來構建 iO。它從理論角度提供了一種即時構建多個加密工具的方式，而這在之前是不可能的。例如，它允許創建「可否認」加密和「函數」加密。以色列理工學院教授 Yuval Ishai 曾表示：「現在應該不會有人懷疑 iO 的存在了。」（詳見：《不可區分混淆被實現，電腦科學家摘得這顆密碼學「皇冠上的明珠」）

本文作者之一 Huijia Lin 本科畢業於浙江大學，2011 年在康奈爾大學拿到博士學位，目前在華盛頓大學電腦科學與工程學院擔任副教授。她的主要研究興趣集中在密碼學以及密碼學與其他計算機領域的交叉領域，如複雜性理論、演算法設計和安全等。

最佳學生論文獎

STOC Danny Lewin 最佳學生論文獎是為了紀念著名數學家和企業家 Danny Lewin 設立的，他曾參與創立網際網路公司 Akamai Technologies。今年共有兩篇論文獲得 Danny Lewin 最佳學生論文獎。

論文 1：Discrepancy Minimization via a Self-Balancing Walk

• 作者：Ryan Alweiss（普林斯頓大學）、Yang P. Liu（斯坦福大學）、Mehtaab Sawhney（麻省理工學院）

• 論文連結：https://arxiv.org/abs/2006.14009

該研究探究了在各種設定下

中向量的差異最小化，在多個維度上分析了一個新的簡單隨機過程。根據研究結果的推論，研究者推算出由 Bansal 等人提出的線上向量平衡中幾個問題的對數因子的嚴格邊界，並提出了 Komlós 猜想的對數邊界的線性時間演算法。

本文作者之一 Yang P. Liu 本科畢業於麻省理工學院，目前在斯坦福大學讀博，主攻數學。他曾在 2014 年和 2015 年拿到過國際數學奧林匹克競賽（IMO）的金獎。除了純數學之外，他還對理論電腦科學感興趣，尤其是演算法設計。

論文 2：Separating Words and Trace Reconstruction

• 作者：Zachary Chase（牛津大學）

• 論文連結：https://dl.acm.org/doi/abs/10.1145/3406325.3451118

該研究證明對於任意不同的 x,y ∈

，存在一個具有 O(n^(1/3)) 狀態的確定有限自動機，它接受 x 但不接受 y。這改進了 Robson 在 1989 年提出的 O(n^(2/5)) 邊界。使用一種類似的複雜分析技術，研究者改進了最壞情況軌跡重建的上限，表明任何未知字元串 x ∈

都能以高概率從 exp(O(n^(1/5))) 獨立生成的跡（trace）中重建。

時間檢驗獎

今年 STOC 的時間檢驗獎頒給了 7 篇論文，距今的時間跨度大約分為 30 年、20 年、10 年三個類別，分別是：

• 論文 1：Completeness theorems for non-cryptographic fault-tolerant distributed computation（STOC 1988）

• 作者：Michael Ben-Or、Shafi Goldwasser、Avi Wigderson

• 論文連結：https://dl.acm.org/doi/10.1145/62212.62213

• 論文 2：Multiparty unconditionally secure protocols（STOC 1988）

• 作者：David Chaum、Claude Crépeau、Ivan Damgrd

• 論文連結：https://dl.acm.org/doi/10.1145/62212.62214

• 論文 3：Verifiable secret-sharing and multiparty protocols with honest majority

• 作者：Tal Rabin、Michael Ben-Or

• 論文連結：https://dl.acm.org/doi/10.1145/73007.73014

• 論文 4：A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries（STOC 2001）

• 作者：Mark Jerrum、Alistair Sinclair、Eric Vigoda

• 論文連結：https://www.cc.gatech.edu/~vigoda/Permanent.pdf

• 論文 5：Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

• 作者：Daniel A. Spielman、Shang-Hua Teng

• 論文連結：https://arxiv.org/pdf/cs/0111050.pdf

• 論文 6：Approximate distance oracles

• 作者：Mikkel Thorup、Uri Zwick

• 論文連結：http://www.cs.jhu.edu/~baruch/teaching/600.427/Papers/oracle-STOC-try.pdf

• 論文 7：The computational complexity of linear optics

• 作者：Scott Aaronson、Alex Arkhipov

• 論文連結：https://arxiv.org/pdf/1011.3245.pdf

論文 5 的作者之一滕尚華是著名的華人學者。他是南加州大學電腦科學與數學系教授，此次獲獎的論文由他和 Daniel A. Spielman 合著。這篇論文在 STOC 2001 上發表，曾獲 ACM 演算法和計算理論特別興趣小組的獎項。如今經過 20 年的時間檢驗，它又摘得 STOC 2021 的時間檢驗獎。

在這篇論文中，滕教授和 Spielman 使用平滑分析的概念為了解演算法效能給出了更實際的理解方法，例如度量其運行時間。這個概念有助於解釋一個現象：為什麼有些演算法在實踐中比理論上更有效？該研究發現，許多演算法，尤其是廣泛使用的線性規劃單純形演算法，只要輸入中有噪聲就可以工作，而現實世界的資料中通常存在噪聲。該研究的發現已應用於無數實用演算法，涉及網際網路通訊、深度學習、資料探勘、差分隱私、博弈論和個性化推薦系統等多個領域。

滕尚華於 1985 年畢業於上海交通大學，獲得電氣工程和電腦科學雙學士學位，1988 年獲得南加州大學電腦科學碩士學位，1991 年獲卡內基梅隆大學 (CMU) 電腦科學博士學位。在受聘于南加州大學之前，他曾在波士頓大學任教，是 Akamai 科技公司高階科學家，麻省理工學院 (MIT) 數學系客座教授，並在 IBM Almaden 研究中心、微軟亞洲研究院等多家學術研究機構兼任研究員。此外，滕尚華教授還是 ACM Fellow。

2008 年，滕尚華教授因在演算法的平滑分析領域的研究成果，獲得理論計算機領域最高獎——哥德爾獎(Gdel Prize)。2009 年獲得由美國數學學會和美國數學規劃學會頒發的富爾克森獎(Fulkerson Prize)。他曾被西蒙斯基金會評為「世界上最具原創性的理論科學家」之一。