Paper Info
Title
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).\r\nApplying the principle to cryptographic pseudorandom generators, we introduce\r\n- 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|).\r\nIf 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 O(√n) to O(log n).\r\nApplying 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 \r\n- 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.\r\nA 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.\r\nWe 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.
Year
DOI
Venue
2020
10.4230/LIPIcs.CCC.2020.20
CCC
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
1
Name
Order
Citations
PageRank
Shuichi Hirahara137.48