Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > NEEKON VAFA:
All reports by Author Neekon Vafa:

TR21-166 | 21st November 2021
Lijie Chen, Shuichi Hirahara, Neekon Vafa

Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions

What is a minimal worst-case complexity assumption that implies non-trivial average-case hardness of NP or PH? This question is well motivated by the theory of fine-grained average-case complexity and fine-grained cryptography. In this paper, we show that several standard worst-case complexity assumptions are sufficient to imply non-trivial average-case hardness ... more >>>




ISSN 1433-8092 | Imprint