Chen, Lijie ;
Hirahara, Shuichi ;
Vafa, Neekon
AverageCase Hardness of NP and PH from WorstCase FineGrained Assumptions
Abstract
What is a minimal worstcase complexity assumption that implies nontrivial averagecase hardness of NP or PH? This question is well motivated by the theory of finegrained averagecase complexity and finegrained cryptography. In this paper, we show that several standard worstcase complexity assumptions are sufficient to imply nontrivial averagecase hardness of NP or PH:
 NTIME[n] cannot be solved in quasilinear time on average if UP ̸ ⊆ DTIME[2^{Õ(√n)}].
 Σ₂TIME[n] cannot be solved in quasilinear time on average if Σ_kSAT cannot be solved in time 2^{Õ(√n)} for some constant k. Previously, it was not known if even averagecase hardness of Σ₃SAT implies the averagecase hardness of Σ₂TIME[n].
 Under the ExponentialTime Hypothesis (ETH), there is no averagecase n^{1+ε}time algorithm for NTIME[n] whose running time can be estimated in time n^{1+ε} for some constant ε > 0.
Our results are given by generalizing the nonblackbox worstcasetoaveragecase connections presented by Hirahara (STOC 2021) to the settings of finegrained complexity. To do so, we construct quite efficient complexitytheoretic pseudorandom generators under the assumption that the nondeterministic linear time is easy on average, which may be of independent interest.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs.ITCS.2022.45,
author = {Chen, Lijie and Hirahara, Shuichi and Vafa, Neekon},
title = {{AverageCase Hardness of NP and PH from WorstCase FineGrained Assumptions}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {45:145:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15641},
URN = {urn:nbn:de:0030drops156411},
doi = {10.4230/LIPIcs.ITCS.2022.45},
annote = {Keywords: Averagecase complexity, worstcase to averagecase reduction}
}
25.01.2022
Keywords: 

Averagecase complexity, worstcase to averagecase reduction 
Seminar: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Issue date: 

2022 
Date of publication: 

25.01.2022 