Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JIATU LI:
All reports by Author Jiatu Li:

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

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


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

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


TR21-023 | 20th February 2021
Jiatu Li, Tianqi Yang

$3.1n - o(n)$ Circuit Lower Bounds for Explicit Functions

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




ISSN 1433-8092 | Imprint