All reports by Author Tianqi Yang:

__
TR22-086
| 9th June 2022
__

Lijie Chen, Jiatu Li, Tianqi Yang#### Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs

Revisions: 1

__
TR21-125
| 23rd August 2021
__

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

Revisions: 1

__
TR21-023
| 20th February 2021
__

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

Lijie Chen, Jiatu Li, Tianqi Yang

In a recent work, Fan, Li, and Yang (STOC 2022) constructed a family of almost-universal hash functions such that each function in the family is computable by $(2n + o(n))$-gate circuits of fan-in $2$ over the $B_2$ basis. Applying this family, they established the existence of pseudorandom functions computable by ... more >>>

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 >>>