姚班本科生摘最佳学生论文奖，计算机理论顶会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