Zhiyuan Fan, Jiatu Li, and Tianqi Yang from Yao Class, Tsinghua University received a Best Student Paper Award at the 54th Annual ACM Symposium on Theory of Computing (STOC 2022) for the paper, “The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity”.

Pseudorandom function (PRF), capturing the indistinguishability of a set of functions from a random function, is a cornerstone of cryptography. The amount of computational resource we need for cryptography is an important question of both theoretical and practical interests. In this paper, they study the problem on pseudorandom functions (PRFs) in the context of circuit complexity, and surprisingly, prove extremely tight upper and lower bounds in various circuit models. As a byproduct, they also prove unconditional tight upper and lower bounds for “almost” universal hashing, which is of independent interests. Their results make progress in realizing the limitation of the “bootstrapping results” in computational complexity.

a depth-2 linear threshold circuit

ACM Symposium on Theory of Computing (STOC) is a prestigious CS theory conference and will take place in Rome, Italy in 2022. This year, 135 papers were selected from 457 submissions for the conference with a paper acceptance rate of 29 percent. Besides, 7 other papers by IIIS faculty, students and alumni have been also accepted to STOC 2022.