License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2022.25
URN: urn:nbn:de:0030-drops-165875
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16587/
Go to the corresponding LIPIcs Volume Portal

Hirahara, Shuichi ; Nanashima, Mikito

Finding Errorless Pessiland in Error-Prone Heuristica

pdf-format:
LIPIcs-CCC-2022-25.pdf (0.9 MB)

Abstract

Average-case complexity has two standard formulations, i.e., errorless complexity and error-prone complexity. In average-case complexity, a critical topic of research is to show the equivalence between these formulations, especially on the average-case 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 error-prone 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 meta-complexity: GapMINKT^? ∉ prSIZE^?[2^o(n/log n)] and GapMCSP^? ∉ prSIZE^?[2^(n^ε)] for some ε > 0.
- Worst-case 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.
- Average-case hardness of distribution-free 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 auxiliary-input one-way function, an auxiliary-input pseudorandom generator, and an auxiliary-input pseudorandom function against SIZE^?[2^o(n/log n)].
This provides considerable insights into Pessiland (i.e., the world in which no one-way function exists, and NP is hard on average), such as the relativized separation of the error-prone average-case hardness of NP and auxiliary-input 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 Error-Prone Heuristica}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{25:1--25:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16587},
  URN =		{urn:nbn:de:0030-drops-165875},
  doi =		{10.4230/LIPIcs.CCC.2022.25},
  annote =	{Keywords: average-case complexity, oracle separation, relativization barrier, meta-complexity, learning, auxiliary-input cryptography}
}

Keywords: average-case complexity, oracle separation, relativization barrier, meta-complexity, learning, auxiliary-input cryptography
Collection: 37th Computational Complexity Conference (CCC 2022)
Issue Date: 2022
Date of publication: 11.07.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI