Generalized and Unified Equivalences between Hardness and Pseudoentropy
- LecturerMr. Hsien-En Tzeng (Sokendai)
Host: Kai-Min Chung - Time2026-09-16 (Wed.) 10:15 ~ 12:15
- LocationAuditorium 101 at IIS new Building
Abstract
The equivalence between hardness and pseudoentropy is used to construct PRGs from OWFs and to prove Impagliazzo’s Hardcore Lemma (see Zheng’s Thesis http://nrs.harvard.edu/urn-3:HUL.InstRepos:11745716). I will present these applications and sketch Hu and Vadhan’s (TCC 2025, https://arxiv.org/abs/2507.05972) proof of the equivalence through the Enhanced Leakage-Simulation Lemma, inspired by the Multicalibration Theorem in the algorithmic fairness literature.