License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2020.20
URN: urn:nbn:de:0030-drops-125720
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12572/
Hirahara, Shuichi
Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions
Abstract
The standard notion of promise problem is a pair of disjoint sets of instances, each of which is regarded as Yes and No instances, respectively, and the task of solving a promise problem is to distinguish these two sets of instances. In this paper, we introduce a set of new promise problems which are conjectured to be non-disjoint, and prove that hardness of these "non-disjoint" promise problems gives rise to the existence of hitting set generators (and vice versa). We do this by presenting a general principle which converts any black-box construction of a pseudorandom generator into the existence of a hitting set generator whose security is based on hardness of some "non-disjoint" promise problem (via a non-black-box security reduction).
Applying the principle to cryptographic pseudorandom generators, we introduce
- The Gap(K^SAT vs K) Problem: Given a string x and a parameter s, distinguish whether the polynomial-time-bounded SAT-oracle Kolmogorov complexity of x is at most s, or the polynomial-time-bounded Kolmogorov complexity of x (without SAT oracle) is at least s + O(log|x|).
If Gap(K^SAT vs K) is NP-hard, then the worst-case and average-case complexity of PH is equivalent. Under the plausible assumption that E^NP ≠ E, the promise problem is non-disjoint. These results generalize the non-black-box worst-case to average-case reductions of Hirahara [Hirahara, 2018] and improve the approximation error from Õ(√n) to O(log n).
Applying the principle to complexity-theoretic pseudorandom generators, we introduce a family of Meta-computational Circuit Lower-bound Problems (MCLPs), which are problems of distinguishing the truth tables of explicit functions from hard functions. Our results generalize the hardness versus randomness framework and identify problems whose circuit lower bounds characterize the existence of hitting set generators. For example, we introduce
- The E vs SIZE(2^o(n)) Problem: Given the truth table of a function f, distinguish whether f is computable in exponential time or requires exponential-size circuits to compute.
A nearly-linear AC⁰ ∘ XOR circuit size lower bound for this promise problem is equivalent to the existence of a logarithmic-seed-length hitting set generator for AC⁰ ∘ XOR. Under the plausible assumption that E ⊈ SIZE(2^o(n)), the promise problem is non-disjoint (and thus the minimum circuit size is infinity). This is the first result that provides the exact characterization of the existence of a hitting set generator secure against ℭ by the worst-case lower bound against ℭ for a circuit class ℭ = AC⁰ ∘ XOR ⊂ TC⁰. In addition, we prove that a nearly-linear size lower bound against co-nondeterministic read-once branching programs for some "non-disjoint" promise problem is sufficient for resolving RL = L.
We also establish the equivalence between the existence of a derandomization algorithm for uniform algorithms and a uniform lower bound for a problem of approximating Levin’s Kt-complexity.
BibTeX - Entry
@InProceedings{hirahara:LIPIcs:2020:12572,
author = {Shuichi Hirahara},
title = {{Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions}},
booktitle = {35th Computational Complexity Conference (CCC 2020)},
pages = {20:1--20:47},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-156-6},
ISSN = {1868-8969},
year = {2020},
volume = {169},
editor = {Shubhangi Saraf},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12572},
URN = {urn:nbn:de:0030-drops-125720},
doi = {10.4230/LIPIcs.CCC.2020.20},
annote = {Keywords: meta-complexity, pseudorandom generator, hitting set generator}
}
|
Keywords: |
|
meta-complexity, pseudorandom generator, hitting set generator |
|
Collection: |
|
35th Computational Complexity Conference (CCC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
17.07.2020 |
