姚班本科生摘最佳學生論文獎，計算機理論頂會STOC2022獎項公布

日前，STOC 2022 官網公布了論文接收列表，其中共有 2 篇最佳論文和 2 篇最佳學生論文。

作為計算機理論領域的全球頂級學術會議，ACM 計算理論年會（ACM Symposium on Theory of Computing, STOC）始于 1969 年，今年已經來到了第 54 屆。本屆會議將于 6 月 20 日至 24 日在意大利羅馬舉行。
該會議由 ACM SIGACT (Special Interest Group in Algorithms and Computation Theory) 主辦，歷年會議涵蓋的領域十分廣泛，包括算法和數據結構、計算復雜性、密碼學、計算幾何、組合學、隨機與去隨機化、算法博弈論和量子計算等。
STOC 在整個計算機科學領域享有崇高的聲望，屬于公認難度最高的會議之一。與 AI 不同，計算機理論領域被認為是國內學界與全球頂級水平相距較大的方向，在 STOC 大會中，2000-2017 年大陸研究機構平均每年發表的論文數量僅為 0.89 篇。
目前，從 STOC 2022 官網公布的信息中，我們可以找到今年的兩篇最佳論文和兩篇最佳學生論文。其中，清華大學姚班本科生范致遠（計科 91）、李嘉圖（計科 92）和楊天祺（計科 92）的論文獲得了其中一個最佳學生論文獎。

接下來對四篇獲獎論文進行簡要的介紹。
最佳論文
論文 1：Locally Testable Codes with constant rate, distance, and locality

• 論文地址：https://arxiv.org/pdf/2111.04808.pdf

• 作者：Irit Dinur、 Shai Evra、 Ron Livne、 Alexander Lubotzky、 Shahar Mozes

• 機構：魏茨曼科學研究所、希伯來大學

論文摘要：本地可測試代碼（locally testable code, LTC）是具有屬性測試器的糾錯代碼。測試者讀取隨機選擇的 q 個比特，并以與它們和代碼之間的距離成正比的概率拒絕單詞。參數 q 為被稱為測試者的位置。
LTC 最開始是作為 PCP 的重要組件進行研究的，此后便發展成為單獨的主題了。高速率 LTC 在實踐中可能非常有用：在嘗試對接收到的字進行解碼之前，我們首先可以通過快速測試它是否接近代碼來節省時間。不過，一個尚未解決的問題在于是否存在「c^3-LTCs」，即具有恒定速率、恒定距離和恒定位置的 LTC。
在本文中，研究者基于一個新的二維復合體構建這樣的代碼，并稱之為「左右 Cayley 復合體」。這本質上是一個圖，除了點和邊之外還有正方形。他們的代碼可以被視為（一維）擴展器代碼的二維版本，其中代碼字是正方形而非邊上的函數。
算法 1：迭代解碼算法。
論文 2：Asymptotically Good Quantum and Locally Testable Classical LDPC Codes

• 論文地址：https://arxiv.org/abs/2111.03654

• 作者：Pavel Panteleev、Gleb Kalachev

• 機構：莫斯科國立大學

論文摘要：該論文研究了通過非阿貝爾群上的 lifted product 構造獲得恒定速率的經典和量子 LDPC 碼，證明所獲得的量子 LDPC 碼族是漸近良好的，這進一步證明了 qLDPC 猜想。此外，研究者還證明生成的經典 LDPC 碼在具有恒定查詢和健全性參數的情況下也是漸近良好的，并具有局部可測試性，這驗證了局部可測試碼領域一個眾所周知的猜想。
最佳學生論文
論文 1：The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs

• 論文地址：https://eccc.weizmann.ac.il/report/2021/125

• 作者：范致遠、李嘉圖、楊天祺

• 機構：清華大學

論文摘要：密碼學需要多少計算資源？這是一個既有理論意義又有實際意義的重要問題。本文研究了電路復雜性背景下的偽隨機函數（pseudorandom functions，PRFs）問題。令人驚訝的是，該研究在各種電路模型中證明了極其嚴格的上限和下限。

• 在一般的 B_2 電路中，假設存在 PRF，PRF 可以構建為 2n + o(n) 大小，這簡化和改進了 Ishai 等人限制的 O(n)。該研究通過給出無條件的 2n - O(1) 下限來證明這種構造幾乎是最優的；

• 在對數深度電路（logarithmic depth circuits）中，假設存在 NC^1 PRF，PRF 可以同時構建為 2n + o(n) 大小和 (1 + ε)log n 深度；

• 在恒定深度線性閾值電路中，假設存在 TC^0 PRF，PRF 可以用導線復雜度構建。該研究還給出了某個常數 c 的 線復雜度下限。

值得一提的是，這篇獲獎論文的三位作者范致遠（計科 91）、李嘉圖（計科 92）、楊天祺（計科 92），他們都是清華姚班本科生。三個人均以保送方式進入清華大學， 楊天祺、李嘉圖還曾榮獲第 44 屆 ICPC 國際大學生程序設計競賽東亞大陸決賽金牌。 
論文 2：The Optimal Error Resilience of Interactive Communication Over Binary Channels

• 論文地址：https://arxiv.org/pdf/2110.15395.pdf

• 作者：Meghal Gupta、 Rachel Yun Zhang

• 機構：微軟研究院、MIT

論文摘要：在交互式編碼中，Alice 和 Bob 希望計算它們各自私有輸入 x 和 y 的某個函數 f，并通過參與非自適應（固定順序和固定長度）交互式協議進行聯合計算 f(x, y) 。它們的目標是以一種容錯方式做到，這樣一來，即使對協議施加了部分對抗性破壞，雙方仍可以學習 f(x, y)。
在這項工作中，研究者探究了這種協議在面對對抗性位翻轉性或擦除時的最優抗誤碼能力。雖然這種協議在大型字母表上的最優抗誤碼能力是眾所周知的，但在二進制字母表上的情況仍然未知。因此，研究者解決了在二進制信道上確定最優抗誤碼能力。
具體而言，研究者構建的協議能夠在二進制位翻轉信道上實現 1/6 抗誤碼和在二進制擦除信道上實現 1/2 抗誤碼，這兩者的匹配上限都是已知的。他們還注意到，二進制位翻轉協議的通信復雜度在輸入大小上是多項式的，而二進制擦除協議的通信復雜度在最小無噪聲協議計算 f 的大小上是線性的。
協議 1。
參考鏈接：http://acm-stoc.org/stoc2022/http://acm-stoc.org/stoc2022/STOCprogram.html