機器之心報道機器之心編輯部日前 STOC 2022 官網公布瞭論文接收列錶 姚班本科生摘最佳學生論文奬，計算機理論頂會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