近日，计算机科学领域顶级国际会议第54届ACM计算理论年会（STOC 2022 54th Annual Symposium on the Theory of Computing）官网公布，清华大学交叉信息研究院师生及校友共有7篇论文被接收，其中计科班（简称“姚班”）91班范致远、计科92班李嘉图与杨天祺三位同学共同完成的论文“伪随机函数的精确复杂性与计算复杂性理论中自举现象的黑盒自然证明障碍”（The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity）被大会接收，并获评最佳学生论文。

伪随机函数（pseudorandom functions）是无法与随机函数区分开的函数族。它作为密码学许多构造的起点，是密码学的基础。因此构造高效的伪随机函数在理论及应用中有多种意义。该论文研究了伪随机函数的电路复杂性，在多个重要的电路复杂性类中对伪随机函数给出了紧的上界与下界。例如证明了在一般电路中，若多项式大小的电路可计算的伪随机函数存在，则存在一个仅需大约2n个门的电路族即可计算的伪随机函数。同时，该研究无条件地证明了计算任何伪随机函数至少需要2n-2个门。

论文插图：两层线性阈门电路

这些上下界结果为电路复杂性理论提供了新的理解，也解释了为何一些广为相信的猜想难以被证明。特别地，针对目前电路复杂性理论中存在的“自举现象”（bootstrapping phenomena），该研究指出，要想从这些现象推出P vs NP等重要开放问题的答案，还需要一些全新的证明思路。

ACM计算理论年会（STOC）是理论计算机科学领域最顶级的国际会议，在整个计算机科学领域享有崇高的声望，并被公认是难度最高的会议之一。STOC2022将于意大利罗马召开，本次会议共接收论文投稿457篇，录用135篇，接收率约为29%。