Abstract
Averagecase complexity has two standard formulations, i.e., errorless complexity and errorprone complexity. In averagecase complexity, a critical topic of research is to show the equivalence between these formulations, especially on the averagecase complexity of NP.
In this study, we present a relativization barrier for such an equivalence. Specifically, we construct an oracle relative to which NP is easy on average in the errorprone setting (i.e., DistNP ⊆ HeurP) but hard on average in the errorless setting even by 2^o(n/log n)size circuits (i.e., DistNP ⊈ AvgSIZE[2^o(n/log n)]), which provides an answer to the open question posed by Impagliazzo (CCC 2011). Additionally, we show the following in the same relativized world:
 Lower bound of metacomplexity: GapMINKT^? ∉ prSIZE^?[2^o(n/log n)] and GapMCSP^? ∉ prSIZE^?[2^(n^ε)] for some ε > 0.
 Worstcase hardness of learning on uniform distributions: P/poly is not weakly PAC learnable with membership queries on the uniform distribution by nonuniform 2ⁿ/n^ω(1)time algorithms.
 Averagecase hardness of distributionfree learning: P/poly is not weakly PAC learnable on average by nonuniform 2^o(n/log n)time algorithms.
 Weak cryptographic primitives: There exist a hitting set generator, an auxiliaryinput oneway function, an auxiliaryinput pseudorandom generator, and an auxiliaryinput pseudorandom function against SIZE^?[2^o(n/log n)].
This provides considerable insights into Pessiland (i.e., the world in which no oneway function exists, and NP is hard on average), such as the relativized separation of the errorprone averagecase hardness of NP and auxiliaryinput cryptography. At the core of our oracle construction is a new notion of random restriction with masks.
BibTeX  Entry
@InProceedings{hirahara_et_al:LIPIcs.CCC.2022.25,
author = {Hirahara, Shuichi and Nanashima, Mikito},
title = {{Finding Errorless Pessiland in ErrorProne Heuristica}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {25:125:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772419},
ISSN = {18688969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16587},
URN = {urn:nbn:de:0030drops165875},
doi = {10.4230/LIPIcs.CCC.2022.25},
annote = {Keywords: averagecase complexity, oracle separation, relativization barrier, metacomplexity, learning, auxiliaryinput cryptography}
}
Keywords: 

averagecase complexity, oracle separation, relativization barrier, metacomplexity, learning, auxiliaryinput cryptography 
Collection: 

37th Computational Complexity Conference (CCC 2022) 
Issue Date: 

2022 
Date of publication: 

11.07.2022 