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

Lijie Chen, Shuichi Hirahara, Neekon Vafa

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