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

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

接下來對四篇獲獎?wù)撐倪M行簡要的介紹。
最佳論文
論文 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

• 機構(gòu)：魏茨曼科學研究所、希伯來大學

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

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

• 作者：Pavel Panteleev、Gleb Kalachev

• 機構(gòu)：莫斯科國立大學

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

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

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

• 機構(gòu)：清華大學

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

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

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

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

值得一提的是，這篇獲獎?wù)撐牡娜蛔髡叻吨逻h（計科 91）、李嘉圖（計科 92）、楊天祺（計科 92），他們都是清華姚班本科生。三個人均以保送方式進入清華大學， 楊天祺、李嘉圖還曾榮獲第 44 屆 ICPC 國際大學生程序設(shè)計競賽東亞大陸決賽金牌。 
論文 2：The Optimal Error Resilience of Interactive Communication Over Binary Channels

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

• 作者：Meghal Gupta、 Rachel Yun Zhang

• 機構(gòu)：微軟研究院、MIT

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