Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with explicit obstruction:
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 >>>

ISSN 1433-8092 | Imprint