Zhiyuan Fan, Jiatu Li, and Tianqi Yang from the 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 interest. In their paper, they studied the problem of pseudorandom functions (PRFs) in the context of circuit complexity, and surprisingly, proved extremely tight upper and lower bounds in various circuit models. As a byproduct, they also proved unconditional tight upper and lower bounds for “almost” universal hashing, which is of independent interest. Their results made progress in realizing the limitations of the “bootstrapping results” in computational complexity.

a depth-2 linear threshold circuit

The 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%. In addition, 7 other papers by IIIS faculty, students and alumni have been also accepted for STOC 2022.

From IIIS 

Editors：John Olbrich, Li Han