Hirahara, Shuichi
NonDisjoint Promise Problems from MetaComputational 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 nondisjoint, and prove that hardness of these "nondisjoint" 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 blackbox construction of a pseudorandom generator into the existence of a hitting set generator whose security is based on hardness of some "nondisjoint" promise problem (via a nonblackbox 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 polynomialtimebounded SAToracle Kolmogorov complexity of x is at most s, or the polynomialtimebounded Kolmogorov complexity of x (without SAT oracle) is at least s + O(logx).
If Gap(K^SAT vs K) is NPhard, then the worstcase and averagecase complexity of PH is equivalent. Under the plausible assumption that E^NP ≠ E, the promise problem is nondisjoint. These results generalize the nonblackbox worstcase to averagecase reductions of Hirahara [Hirahara, 2018] and improve the approximation error from Õ(√n) to O(log n).
Applying the principle to complexitytheoretic pseudorandom generators, we introduce a family of Metacomputational Circuit Lowerbound 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 exponentialsize circuits to compute.
A nearlylinear AC⁰ ∘ XOR circuit size lower bound for this promise problem is equivalent to the existence of a logarithmicseedlength hitting set generator for AC⁰ ∘ XOR. Under the plausible assumption that E ⊈ SIZE(2^o(n)), the promise problem is nondisjoint (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 worstcase lower bound against ℭ for a circuit class ℭ = AC⁰ ∘ XOR ⊂ TC⁰. In addition, we prove that a nearlylinear size lower bound against conondeterministic readonce branching programs for some "nondisjoint" 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 Ktcomplexity.
BibTeX  Entry
@InProceedings{hirahara:LIPIcs:2020:12572,
author = {Shuichi Hirahara},
title = {{NonDisjoint Promise Problems from MetaComputational View of Pseudorandom Generator Constructions}},
booktitle = {35th Computational Complexity Conference (CCC 2020)},
pages = {20:120:47},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771566},
ISSN = {18688969},
year = {2020},
volume = {169},
editor = {Shubhangi Saraf},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12572},
URN = {urn:nbn:de:0030drops125720},
doi = {10.4230/LIPIcs.CCC.2020.20},
annote = {Keywords: metacomplexity, pseudorandom generator, hitting set generator}
}
17.07.2020
Keywords: 

metacomplexity, pseudorandom generator, hitting set generator 
Seminar: 

35th Computational Complexity Conference (CCC 2020)

Issue date: 

2020 
Date of publication: 

17.07.2020 