All reports by Author Tianqi Yang:

__
TR21-125
| 23rd August 2021
__

Zhiyuan Fan, Jiatu Li, Tianqi Yang#### The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs

__
TR21-023
| 20th February 2021
__

Jiatu Li, Tianqi Yang#### $3.1n - o(n)$ Circuit Lower Bounds for Explicit Functions

Zhiyuan Fan, Jiatu Li, Tianqi Yang

How much computational resource do we need for cryptography? This is an important question of both theoretical and practical interests. In this paper, we study the problem on pseudorandom functions (PRFs) in the context of circuit complexity. Perhaps surprisingly, we prove extremely tight upper and lower bounds in various circuit ... more >>>

Jiatu Li, Tianqi Yang

Proving circuit lower bounds has been an important but extremely hard problem for decades. Although one may show that almost every function $f:\mathbb{F}_2^n\to\mathbb{F}_2$ requires circuit of size $\Omega(2^n/n)$ by a simple counting argument, it remains unknown whether there is an explicit function (for example, a function in $NP$) not computable ... more >>>