姚班本科生摘最佳學(xué)生論文獎，計(jì)算機(jī)理論頂會STOC2022獎項(xiàng)公布

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

作為計(jì)算機(jī)理論領(lǐng)域的全球頂級學(xué)術(shù)會議，ACM 計(jì)算理論年會（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)、計(jì)算復(fù)雜性、密碼學(xué)、計(jì)算幾何、組合學(xué)、隨機(jī)與去隨機(jī)化、算法博弈論和量子計(jì)算等。
STOC 在整個計(jì)算機(jī)科學(xué)領(lǐng)域享有崇高的聲望，屬于公認(rèn)難度最高的會議之一。與 AI 不同，計(jì)算機(jī)理論領(lǐng)域被認(rèn)為是國內(nèi)學(xué)界與全球頂級水平相距較大的方向，在 STOC 大會中，2000-2017 年大陸研究機(jī)構(gòu)平均每年發(fā)表的論文數(shù)量僅為 0.89 篇。
目前，從 STOC 2022 官網(wǎng)公布的信息中，我們可以找到今年的兩篇最佳論文和兩篇最佳學(xué)生論文。其中，清華大學(xué)姚班本科生范致遠(yuǎn)（計(jì)科 91）、李嘉圖（計(jì)科 92）和楊天祺（計(jì)科 92）的論文獲得了其中一個最佳學(xué)生論文獎。

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

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

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

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

• 作者：Pavel Panteleev、Gleb Kalachev

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

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

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

• 作者：范致遠(yuǎn)、李嘉圖、楊天祺

• 機(jī)構(gòu)：清華大學(xué)

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

• 在一般的 B_2 電路中，假設(shè)存在 PRF，PRF 可以構(gòu)建為 2n + o(n) 大小，這簡化和改進(jì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 可以用導(dǎo)線復(fù)雜度構(gòu)建。該研究還給出了某個常數(shù) c 的 線復(fù)雜度下限。

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

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

• 作者：Meghal Gupta、 Rachel Yun Zhang

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

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