Authors Shuichi Hirahara,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61
www.theoryofcomputing.org
S PECIAL ISSUE : CCC 2020
Non-Disjoint Promise Problems from
Meta-Computational View of
Pseudorandom Generator Constructions
Shuichi Hirahara∗
Received August 18, 2020; Revised September 26, 2022; Published October 14, 2023
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(KSAT vs K) problem, which asks to distinguish strings whose time-bounded
A conference version of this paper appeared in the Proceedings of the 35th Computational Complexity Conference,
2020 [34].
∗ Supported by ACT-I, JST and JSPS KAKENHI Grant Number 18H04090.
ACM Classification: F.1.3
AMS Classification: 68Q15
Key words and phrases: pseudorandom generator, hitting set generator, meta-complexity,
Levin’s Kt complexity, minimum circuit size problem
© 2023 Shuichi Hirahara
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2023.v019.a004
S HUICHI H IRAHARA
SAT-oracle Kolmogorov complexity is small from strings whose time-bounded
Kolmogorov complexity (without SAT oracle) is large. We show that if this problem
is NP-hard, the worst-case and average-case complexities of PH are equivalent. This
generalizes the non-black-box worst-case to average-case reductions of Hirahara
√
(FOCS’18) and improve the approximation error from 𝑂( e 𝑛) to 𝑂(log 𝑛).
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.
We also establish the equivalence between the existence of a non-trivial deran-
domization algorithm for uniform algorithms and a uniform lower bound for a
problem of approximating Levin’s Kt-complexity.
1 Introduction
A promise problem, introduced by Even, Selman, and Yacobi [19], is a pair of disjoint sets
(ΠYes , ΠNo ) that are regarded as the sets of Yes and No instances, respectively. The problem is
regarded as a problem whose instances are “promised” to come from ΠYes ∪ ΠNo . Specifically, an
algorithm 𝐴 is said to solve a promise problem (ΠYes , ΠNo ) if 𝐴 accepts any instance 𝑥 ∈ ΠYes and
rejects any instance 𝑥 ∈ ΠNo ; the behavior of 𝐴 on any “unpromised” instance 𝑥 ∉ ΠYes ∪ΠNo can
be arbitrary. The notion of promise problem is crucial for formalizing several important concepts
and theorems in complexity theory. A canonical example is the unique satisfiability problem
(1SAT , UNSAT), where 1SAT is the set of formulas that has a unique satisfying assignment, and
UNSAT is the set of unsatisfiable formulas. The promise problem is a standard Promise-UP-
complete problem, and the celebrated theorem of Valiant and Vazirani [75] states that it is in fact
NP-hard under randomized reductions. The reader is referred to the survey of Goldreich [24]
for more background on promise problems.
Usually, it is required that ΠYes and ΠNo are disjoint, i. e., ΠYes ∩ ΠNo = ∅. The reason is that
if there exists an instance 𝑥 ∈ ΠYes ∩ ΠNo , then no algorithm can solve the promise problem
(ΠYes , ΠNo ). Indeed, if there were an algorithm 𝐴 that solves (ΠYes , ΠNo ), then 𝐴 must accept 𝑥
and simultaneously reject 𝑥, which is impossible. For this reason, every definition of promise
problems considered before is, to the best of our knowledge, always disjoint.
In this paper, we introduce a set of new promise problems which are conjectured to be non-
disjoint. We will demonstrate that these “non-disjoint” promise problems are worth investigating,
by showing that hardness results for our promise problems have important consequences in
complexity theory. The fact that the promise problems are conjectured to be non-disjoint
means that solving promise problems are conjectured to be impossible, no matter how long
an algorithm is allowed to run. Nevertheless, under several (implausible) assumptions, we
show that “non-disjoint” promise problems can be efficiently solved; in other words, the promise
problems are not only disjoint but also can be shown to be disjoint in a “constructive” way.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 2
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
Taking the contrapositive, we prove that mild hardness results for computing “non-disjoint”
promise problems, which is conjectured to be impossible, are sufficient to resolve important open
questions of complexity theory.
To be more specific, we consider open questions of whether there exists an explicit hitting
set generator. A hitting set generator (HSG) 𝐺 = {𝐺 𝑛 : {0, 1} 𝑠(𝑛) → {0, 1} 𝑛 } 𝑛∈ℕ secure against a
class ℭ is a family of functions 𝐺 𝑛 such that any algorithm 𝐴 ∈ ℭ that accepts at least a half of
the 𝑛-bit strings must accept a string 𝐺 𝑛 (𝑧) for some seed 𝑧 ∈ {0, 1} 𝑠(𝑛) , for all large 𝑛 ∈ ℕ . The
existence of a secure hitting set generator makes it possible to derandomize any one-sided-error
ℭ-randomized algorithm, by simply trying all possible 𝑠(𝑛)-bit seeds 𝑧 and using 𝐺 𝑛 (𝑧) as a
source of randomness. A stronger notion called a pseudorandom generator (PRG) enables us to
derandomize two-sided-error randomized algorithms.
1.1 Meta-computational view of PRG constructions
A standard approach for constructing pseudorandom generators is to use the hardness versus
randomness framework developed in, e. g., [77, 7, 56, 6, 41, 44, 68, 48]. One of the landmark results
of Impagliazzo and Wigderson [44] states that if there exists a function in E = DTIME(2𝑂(𝑛) )
that is not computable by a circuit of size 2𝛼𝑛 for some constant 𝛼 > 0, then there exists a
logarithmic-seed-length pseudorandom generator secure against linear-size circuits (and, in
particular, P = BPP follows). In general, such a result is proved by using a black-box pseudorandom
generator construction 𝐺 (-) that converts any hard function 𝑓 ∉ SIZE(2𝑜(𝑛) ) to a pseudorandom
𝛼𝑛
generator 𝐺 𝑓 : {0, 1} 𝑂(𝑛) → {0, 1}2 secure against circuits of size 2𝛼𝑛 , where 𝛼 > 0 is some
constant.
The underlying theme of this paper is to view black-box PRG constructions from a meta-
computational perspective. Usually, 𝑓 is regarded as a fixed hard function such as 𝑓 ∉ SIZE(2𝑜(𝑛) ).
Instead, here we regard 𝑓 as an input to some “non-disjoint” promise problem, and regard
a black-box PRG construction 𝐺 (-) as a reduction that proves the security of some (universal)
hitting set generator based on the hardness of the “non-disjoint” promise problem. This new
perspective can be applied to arbitrary black-box PRG constructions, and it gives rise to a
“non-disjoint” promise problem associated with the black-box PRG construction. For example,
the pseudorandom generator construction of [44] induces the E vs SIZE(2𝑜(𝑛) ) Problem, which is
the problem of distinguishing whether 𝑓 ∈ E/𝑂(𝑛) or 𝑓 ∉ SIZE(2𝑜(𝑛) ), given the truth table of a
function 𝑓 : {0, 1} 𝑛 → {0, 1}. Here, E/𝑂(𝑛) denotes the class of functions that can be computed
in time 2𝑂(𝑛) with 𝑂(𝑛) bits of advice (see Definition 1.10 and Section 4.2 for a precise definition).
There are two types of a pseudorandom generator. One is a cryptographic PRG, which is
computable in polynomial time in its seed length. This notion is useful for building secure
cryptographic primitives. We present in Section 1.2 “non-disjoint” promise problems whose
hardness gives rise to a cryptographic hitting set generator. This provides a new approach
for establishing the equivalence between the worst-case and average-case complexity of PH.
The other is a complexity-theoretic PRG, which is allowed to be computed in time exponential
in its seed length. This notion is sufficient for the purpose of derandomizing randomized
algorithms. In Section 1.3, we generalize the hardness versus randomness framework by using
the meta-computational view of black-box PRG constructions, and establish the equivalence
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 3
S HUICHI H IRAHARA
between circuit lower bounds for “non-disjoint” promise problems and the existence of hitting
set generators. Sections 1.2 and 1.3 can be read independently.
1.2 Worst-case versus average-case complexity of PH
Understanding average-case complexity is a fundamental question in complexity theory. Average-
case hardness of NP is a prerequisite for building secure cryptographic primitives, such as
one-way functions and cryptographic pseudorandom generators. Indeed, it is not hard to see
that if there exists a polynomial-time-computable hitting set generator 𝐺, then checking whether
a given string is in the image of 𝐺 is a problem in NP that is hard on average (in the errorless
sense). In this section, we present a new approach for proving the average-case hardness of PH,
by implicitly constructing a cryptographic hitting set generator.
A fundamental open question in the theory of average-case complexity, pioneered by [51], is
to establish the equivalence between the worst-case and average-case complexity of NP.
Open Question 1.1. Does P ≠ NP imply DistNP ⊄ AvgP?
Here, DistNP ⊄ AvgP is an average-case analogue of NP ≠ P, and it means that there exist a
language 𝐿 ∈ NP and a polynomial-time samplable distribution 𝒟 such that no average-case
polynomial-time algorithm (equivalently, errorless heuristic scheme) can solve 𝐿 on instances
randomly drawn from 𝒟. The reader is referred to the survey of Bogdanov and Trevisan [8] for
the formal definitions of DistNP and AvgP as well as background on average-case complexity.
For large enough complexity classes such as PSPACE and EXP, there is a general technique for
converting any worst-case hard function 𝑓 to some two-sided-error average-case hard function
Enc( 𝑓 ) based on error-correcting codes [68, 71]. Here, the encoded function Enc( 𝑓 ) is computable
in PSPACE given oracle access to 𝑓 ; thus, the worst-case and average-case complexities of such
large complexity classes are known to be equivalent. Viola [76] showed limitations of such an
approach: Enc( 𝑓 ) cannot be computed in the polynomial-time hierarchy PH 𝑓 ; thus, the proof
technique of using error-correcting codes is not sufficient to resolve Open Question 1.1; it could
not even confirm a positive answer to the following weaker open question:
Open Question 1.2. Does PH ≠ P (or, equivalently, P ≠ NP) imply DistPH ⊄ AvgP?
Observe that Open Question 1.2 is an easier question than Open Question 1.1, since PH = P
is known to be equivalent to NP = P.
There are significant obstacles to resolving Open Question 1.1. One is the relativization
barrier due to Impagliazzo [43]. Another is the limits of black-box reductions due to Feigenbaum
and Fortnow [20] and Bogdanov and Trevisan [8]. The limits of black-box reductions are partially
extended to a “barrier” result for Open Question 1.2 in [39].
Recently, a non-black-box worst-case to average-case reduction that is not subject to the
latter barrier was presented in [32]. The reduction shows that solving the problem GapMINKT
of approximating polynomial-time-bounded Kolmogorov complexity in the worst case can
be reduced to solving MINKT on average. We briefly review the definition of GapMINKT
below. For an integer 𝑡 ∈ ℕ and an oracle 𝐴, a 𝑡-time-bounded 𝐴-oracle Kolmogorov complexity
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 4
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
K𝑡,𝐴 (𝑥) of a finite string 𝑥 is defined as the shortest length of a program that prints 𝑥 in 𝑡
steps with oracle access to 𝐴 (see Section 2 for a precise definition). The promise problem
GapMINKT = (ΠYes , ΠNo ) asks for approximating K𝑡 (𝑥) within an additive error of 𝑂( e K𝑡 (𝑥)),
p
and is formally defined as follows: ΠYes consists of (𝑥, 1𝑠 , 1𝑡 ) such that K𝑡 (𝑥) ≤ 𝑠; and ΠNo
√
consists of (𝑥, 1𝑠 , 1𝑡 ) such that Kpoly(|𝑥|,𝑡) (𝑥) > 𝑠 + 𝑂(
e 𝑠).
The result of [32] can be seen as providing an approach for establishing the equivalence
between worst-case and average-case complexity of NP; indeed, proving NP-hardness of
GapMINKT is sufficient for resolving Open Question 1.1 affirmatively. However, the approxi-
√
mation error 𝑂(e 𝑠) caused by the reduction of [32] is not optimal, which makes the question of
proving NP-hardness of GapMINKT potentially harder.
1.2.1 Gap(K𝐴 vs K)
We herein introduce the following “non-disjoint” promise problem.
Definition 1.3. For an oracle 𝐴 and an approximation quality 𝜏 : ℕ × ℕ → ℕ , the problem
Gap𝜏 (K𝐴 vs K) is defined as the following promise problem (ΠYes , ΠNo ).
ΠYes := { (𝑥, 1𝑠 , 1𝑡 ) | K𝑡,𝐴 (𝑥) ≤ 𝑠 },
ΠNo := { (𝑥, 1𝑠 , 1𝑡 ) | K𝜏(|𝑥|,𝑡) (𝑥) > 𝑠 + log 𝜏(|𝑥|, 𝑡) }.
By default, we assume that 𝜏 is some polynomial and write Gap(K𝐴 vs K) ∈ P if there exists
some polynomial 𝜏 such that Gap𝜏 (K𝐴 vs K) ∈ P.
In this paper, we prove
Theorem 1.4. Let 𝐴 be any oracle. If DistNP𝐴 ⊆ AvgP, then Gap(K𝐴 vs K) ∈ P.
An immediate corollary of Theorem 1.4 is an improvement of the reduction of [32], by setting
𝐴 := ∅. In particular, in order to resolve Open Question 1.1, it suffices to prove NP-hardness
of approximating K𝑡 (𝑥) within an additive error of log 𝜏(|𝑥|, 𝑡) given (𝑥, 1𝑡 ) as input, for any
polynomial 𝜏. A key insight for reducing the approximation error is that there are two main
sources of the approximation error in the reduction of [32]: One comes from fixing a random coin
flip sequence, which we remove by using the (complexity-theoretic) pseudorandom generator
constructed by Buhrman, Fortnow, and Pavan [10] under the assumption that DistNP ⊆ AvgP. The
other comes from the advice complexity of a black-box pseudorandom generator construction,
which we reduce by using a “𝑘-wise direct product generator” whose advice complexity is small
[35].
More surprisingly, the promise problem is conjectured to be non-disjoint for 𝐴 := SAT. That is,
it is conjectured to be impossible for any algorithm to solve Gap(KSAT vs K) — no matter how long
the algorithm is allowed to run. Nevertheless, Theorem 1.4 shows that under the assumption
that PH is easy on average, there exists a polynomial-time algorithm for solving Gap(KSAT vs K).
Taking its contrapositive, this means that, in order to resolve DistPH ⊄ AvgP, it suffices to prove
a super-polynomial time lower bound for solving Gap(KSAT vs K), whose time complexity is
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 5
S HUICHI H IRAHARA
conjectured to be infinity (in the sense that there exists no algorithm that can compute the promise
problem).
We now clarify why Gap(KSAT vs K) is conjectured to be non-disjoint. Under the plausible
assumption that ENP ≠ E, it is not hard to see that there are infinitely many strings 𝑥 such that 𝑥
is simultaneously a Yes and No instance; here, the string 𝑥 is defined as the truth table of the
characteristic function of 𝐿 ∈ ENP \ E/𝑂(𝑛) (see Proposition 3.8).
Another corollary of Theorem 1.4 is that under the assumption that DistPH ⊆ AvgP, any
string 𝑥 that can be compressed with SAT oracle in polynomial time can be also compressed
without any oracle. Formally:
Corollary 1.5 (see also Corollary 3.7). If DistPH ⊆ AvgP, then there exists a polynomial 𝜏 such that
K𝜏(|𝑥|,𝑡) (𝑥) ≤ K𝑡,SAT (𝑥) + log 𝜏(|𝑥|, 𝑡)
for any 𝑥 ∈ {0, 1}∗ and 𝑡 ∈ ℕ .
Proof Sketch. Under the assumption, Gap(KSAT vs K) can be solved by some algorithm. Thus
Gap(KSAT vs K) problem must be disjoint, from which the result follows immediately.
Corollary 1.5 provides a new approach for resolving Open Question 1.2. In order to prove
DistPH ⊄ AvgP under the assumption that P ≠ NP, it suffices to find a string 𝑥 that can be
compressed with SAT oracle but cannot be compressed without SAT oracle. In fact, it suffices to
find such a string 𝑥 under the stronger assumption that NP ⊄ P/poly. This is because Pavan,
Santhanam, and Vinodchandran [60] proved NP ⊄ P/poly if the answer to Open Question 1.2 is
negative.
More importantly, Theorem 1.4 suggests a more general approach to Open Question 1.2.
Note that finding a string 𝑥 compressible with SAT oracle but incompressible without any oracle
corresponds to proving the non-disjointness of Gap(KSAT vs K); this amounts to proving the
time complexity of solving Gap(KSAT vs K) is infinity. Theorem 1.4 suggests that it suffices to
prove that a polynomial-time algorithm cannot find a difference between compressible strings
under SAT oracle and incompressible strings without any oracle, under the worst-case hardness
assumption for NP. In other words, it suffices to prove NP-hardness of Gap(KSAT vs K).
Corollary 1.6 (A new approach for Open Question 1.2). Suppose that the Gap(KSAT vs K) problem
is “NP-hard under randomized reductions”1 in the sense that
NP ⊄ BPP =⇒ Gap(KSAT vs K) ∉ P.
Then, Open Question 1.2 is true; that is,
DistPH ⊄ AvgP ⇐⇒ PH ≠ P.
1Here we use the weak notion of “NP-hardness” in order to strengthen the result. Corollary 1.6 remains true even
if one interprets NP-hardness as a randomized reduction from NP.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 6
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
In a typical proof of NP-hardness of a disjoint promise problem Π = (ΠYes , ΠNo ), one needs
to carefully design a reduction 𝑅 from SAT to Π that “preserves” a structure of SAT; i. e.,
any formula 𝜑 ∈ SAT is mapped to 𝑅(𝜑) ∈ ΠYes and any formula 𝜑 ∈ UNSAT is mapped to
𝑅(𝜑) ∈ ΠNo . The task of proving NP-hardness of Gap(KSAT vs K) is potentially much easier:
in principle, 𝑅(𝜑) can be a fixed input 𝑥 that is in the intersection of Yes and No instances
of Gap(KSAT vs K); more generally, if a promise problem Π is non-disjoint, then any problem
is reducible to Π via a reduction that maps every instance to the intersection of Yes and No
instances of Π. It is worth mentioning that proving NP-hardness of Gap(KSAT vs K) is at least as
easy as proving NP-hardness of GapMINKT since GapMINKT is reducible to Gap(KSAT vs K)
via an identity map.
Subsequent to this work, converse directions of Theorem 1.4 and Corollary 1.6 are established
in the following sense [33]: DistPH ⊆ AvgP if and only if Gap(K𝐴 vs K) ∈ P for every oracle
𝐴 ∈ PH. In particular,2 DistPH ⊆ AvgP ⇐⇒ PH = P (Open Question 1.2) if and only if
Gap(K𝐴 vs K) ∈ P for every 𝐴 ∈ PH implies NP ⊆ BPP (“NP-hardness” of Gap(K𝐴 vs K)).
Therefore, the approach to Open Question 1.2 suggested in this work is one of the most general
approaches.
1.2.2 Non-NP-hardness results do not apply
A line of work presented evidence that NP-hardness of MINKT is not likely to be established
under deterministic reductions (e. g., [49, 54, 40, 38]). For example, it is not hard to see that the
proof technique of Murray and Williams [54] (who proved a similar result for MCSP) can be
extended to the case of GapMINKT.
Theorem 1.7 (Essentially in [54]; see [35]). If GapMINKT is NP-hard under many-one deterministic
reductions, then EXP ≠ ZPP.
This result suggests that establishing NP-hardness of GapMINKT under deterministic
reductions is a challenging task. In contrast, we observe that a similar “non-NP-hardness” result
cannot be applied to the “non-disjoint” promise problem.
Proposition 1.8. Assume that NP-hardness of Gap(KSAT vs K) under many-one reductions implies
EXP ≠ ZPP. Then, EXP ≠ ZPP holds unconditionally.
The reason is that Gap(KSAT vs K) is well defined only if EXP ≠ ZPP. More formally:
Proof. There are two cases. Either Gap(KSAT vs K) is disjoint or not disjoint. In the former
case, by Proposition 3.8, we have ENP = E, which implies EXPNP = EXP by a standard padding
argument; thus, we obtain EXP = EXPNP = ZPEXP ≠ ZPP, where the last inequality follows
from a standard translation argument (see, e. g., [11]). In the latter case, there exists a string
𝑥 that is simultaneously a Yes and No instance. A reduction that always maps to 𝑥 defines a
many-one reduction from any problem to Gap(KSAT vs K); thus, EXP ≠ ZPP follows from the
assumption.
2using the fact that P = BPP if DistPH ⊆ AvgP [10]
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 7
S HUICHI H IRAHARA
In light of Proposition 1.8, we leave as an interesting open question whether there is any
barrier explaining the difficulty of proving NP-hardness of the non-disjoint promise problem.
We mention that GapMINKTSAT , which is equivalent to Gap(KSAT vs KSAT ), is known to be
DistNP-hard [35]. In particular, since Gap(KSAT vs KSAT ) is reducible to Gap(KSAT vs K) via an
identity map, the latter is also DistNP-hard. Therefore, in order to present a barrier for proving
NP-hardness of Gap(KSAT vs K), one must exploit a property that holds for NP but does not
hold for DistNP (unless the notion of reducibility is too strong).
1.2.3 Gap(𝐹 vs 𝐹 −1 ): Meta-computational view of HILL’s PRG
We also propose another approach towards Open Question 1.1, by introducing a promise
problem which asks for distinguishing whether a given function is computable by small circuits,
or cannot be inverted by small circuits. Specifically, for an approximation quality 𝜏, we define the
promise problem Gap𝜏 (𝐹 vs 𝐹 −1 ) as follows. Given a size parameter 𝑠 ∈ ℕ and an integer 𝑛 ∈ ℕ
and random access to a function 𝐹 : {0, 1} 𝑛 → {0, 1} 𝑛 , the task is to distinguish the following
two cases:
Yes: 𝐹 is computable by a circuit of size 𝑠.
No: 𝐹 cannot be inverted on average by any 𝐹-oracle circuit of size 𝜏(𝑛, 𝑠).
We show that “NP-hardness” of Gap𝜏 (𝐹 vs 𝐹 −1 ) for every polynomial 𝜏 is enough for
resolving Open Question 1.1. More specifically, we prove
Theorem 1.9. If DistNP ⊆ AvgP, then there exist a polynomial 𝜏 and a coRP-type randomized algorithm
that solves Gap𝜏 (𝐹 vs 𝐹 −1 ) on input (𝑛, 𝑠) in time poly(𝑛, 𝑠). In particular, Open Question 1.1 is true if
Gap𝜏 (𝐹 vs 𝐹 −1 ) is “NP-hard” for every polynomial 𝜏 in the following sense: NP ⊆ BPP follows from the
assumption that Gap𝜏 (𝐹 vs 𝐹 −1 ) admits a coRP-type algorithm.
This is proved by viewing the black-box PRG construction based on any one-way function,
which is given by Håstad, Impagliazzo, Levin, and Luby [30], from the meta-computational
perspective. Our general proof strategy is given in Section 1.4.
It is easy to observe that Gap(𝐹 vs 𝐹 −1 ) is non-disjoint under the existence of a one-way
function, which is one of the most standard cryptographic primitives. Thus, it is widely believed
that Gap(𝐹 vs 𝐹 −1 ) is impossible to solve. Nevertheless, NP-hardness of Gap(𝐹 vs 𝐹 −1 ) is sufficient
for resolving Open Question 1.1.
1.3 Meta-computational circuit lower-bound problems; MCLPs
We now turn our attention to complexity-theoretic hitting set generators. A standard approach
for constructing complexity-theoretic pseudorandom generators is to use the hardness versus
randomness framework, which reduces the task of constructing a pseudorandom generator to
the task of finding an explicit hard function, such as 𝑓 ∈ E \ SIZE(2𝑜(𝑛) ).
It is, however, a widely accepted fact that proving a circuit size lower bound for an explicit
function is extremely hard. Here by an explicit function, we mean that a function is computable
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 8
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
in E = DTIME(2𝑂(𝑛) ). It is an open question whether there exists an exponential-time-computable
function 𝑓 ∈ E that cannot be computed by any circuit of size 4𝑛 (see [21]). On the other hand, a
simple counting argument shows that most functions 𝑓 : {0, 1} 𝑛 → {0, 1} cannot be computed
by circuits of size 2𝛼𝑛 for any constant 𝛼 < 1.
Why is it so difficult to prove a circuit lower bound for an explicit function? We propose to
view this question from a meta-computational perspective. The fact that it is difficult for human
beings to show that an explicit function cannot be computed by small circuits suggests that it
should be also difficult for algorithms to analyze a circuit lower bound. Our results indicate that
if we can make this intuition formal, then we get breakthrough results in complexity theory.
Specifically, we herein introduce a family of new computational problems, which we call
Meta-computational Circuit Lower-bound Problems (MCLPs). These problems ask for distinguishing
the truth table of explicit functions from hard functions. For example, we propose the following
promise problem:
The E vs SIZE(2𝑜(𝑛) ) Problem (informal)3
Given the truth table of a function 𝑓 : {0, 1} 𝑛 → {0, 1}, distinguish whether 𝑓 ∈ E/𝑂(𝑛) or
𝑓 ∉ SIZE(2𝑜(𝑛) ).
Before defining the problem formally, let us first observe that the E vs SIZE(2𝑜(𝑛) ) Problem is
closely related to the open question of whether E ⊄ SIZE(2𝑜(𝑛) ). Indeed, it is not hard to show
that E/𝑂(𝑛) ⊄ SIZE(2𝑜(𝑛) ) if and only if E ⊄ SIZE(2𝑜(𝑛) ) by regarding an advice string as a part
of input. Therefore, the E vs SIZE(2𝑜(𝑛) ) Problem is non-disjoint if and only if E ⊄ SIZE(2𝑜(𝑛) ).
We now define the problem formally. According to the standard notion of advice [46],
the complexity class E/𝑂(𝑛) is defined as a subset of functions 𝑓 : {0, 1}∗ → {0, 1} that are
defined on all the strings of any length. Thus, “ 𝑓 ∈ E/𝑂(𝑛)” does not make sense for a function
𝑓 : {0, 1} 𝑛 → {0, 1}. Instead, we interpret advice by using the notion of Levin’s resource-
bounded Kolmogorov complexity [50] so that the notion of advice is meaningful for a finite
function 𝑓 : {0, 1} 𝑛 → {0, 1}. For a string 𝑥 ∈ {0, 1}∗ , let Kt(𝑥) denote the Levin’s Kolmogorov
complexity of a string 𝑥, which is defined as the minimum of |𝑀| + log 𝑡 over all the programs
𝑀 that output 𝑥 in time 𝑡; here, |𝑀| denotes the description length of 𝑀. The E vs SIZE(2𝑜(𝑛) )
Problem is formally defined as follows.
Definition 1.10. For any functions 𝑡, 𝑠 : ℕ → ℕ , let (ΠYes (𝑡(𝑛)), ΠNo (𝑠(𝑛))) denote the promise
problem defined as
𝑛
ΠYes (𝑡(𝑛)) := { 𝑓 ∈ {0, 1}2 | Kt( 𝑓 ) ≤ log 𝑡(𝑛), 𝑛 ∈ ℕ },
𝑛
ΠNo (𝑠(𝑛)) := { 𝑓 ∈ {0, 1}2 | size( 𝑓 ) > 𝑠(𝑛), 𝑛 ∈ ℕ }.
𝑛
Here, we identity a function 𝑓 : {0, 1} 𝑛 → {0, 1} with its truth table representation 𝑓 ∈ {0, 1}2 ,
and size( 𝑓 ) denotes the minimum size of a circuit that computes 𝑓 .
3This problem may be called the E/𝑂(𝑛) vs SIZE(2𝑜(𝑛) ) Problem; however, for the sake of notational simplicity
(and for the reason described in the following paragraph), we omit “/𝑂(𝑛)” from the name of the problem.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 9
S HUICHI H IRAHARA
The E vs SIZE(2𝑜(𝑛) ) Problem is defined as the family {(ΠYes (2𝑐𝑛 ), ΠNo (2𝛼𝑛 ))} 𝑐,𝛼>0 of the
promise problems. A family {Π} of problems is said to be solved by a class ℭ and denoted by
{Π} ∈ ℭ if every problem in the family is solved by some algorithm in ℭ.
The idea behind Definition 1.10 is that the complexity class E/𝑂(𝑛) can be characterized
as the class of the functions 𝑓 = { 𝑓𝑛 : {0, 1} 𝑛 → {0, 1}} 𝑛∈ℕ such that, for some constant 𝑐,
for all large 𝑛 ∈ ℕ , Kt( 𝑓𝑛 ) ≤ 𝑐𝑛 holds. Indeed, 𝑓 ∈ E/𝑂(𝑛) means that the truth table of 𝑓𝑛
can be described by a Turing machine of description length 𝑂(𝑛) in time 2𝑂(𝑛) for all large 𝑛.
The relationship between complexity classes with advice and resource-bounded Kolmogorov
complexity will be explained in detail in Section 4.2, where we interpret “DTIME(𝑡(𝑛))/𝑎(𝑛)” as
a subset of functions 𝑓 : {0, 1} 𝑛 → {0, 1}.
1.3.1 Meta-computational view of the hardness vs randomness framework
We show that a nearly linear-size AC0 ◦XOR circuit size lower bound for solving the E vs SIZE(2𝑜(𝑛) )
Problem exactly characterizes the existence of a hitting set generator secure against AC0 ◦ XOR.
Here, AC0 ◦ XOR denotes the class of constant-depth circuits that consist of unbounded-fan-in
AND , OR and XOR gates, and XOR gates are allowed to be present only in the bottom later.
Theorem 1.11. The following (Items 1 to 4) are equivalent.
1. There exists a hitting set generator 𝐺 = {𝐺 𝑛 : {0, 1} 𝑂(log 𝑛) → {0, 1} 𝑛 } 𝑛∈ℕ computable in time
𝑛 𝑂(1) and secure against linear-size AC0 ◦ XOR circuits.
2. For all large 𝑁 ∈ ℕ , there exists no AC0 ◦ XOR circuit of size 𝑁 1+𝑜(1) that computes the
E vs SIZE(2𝑜(𝑛) ) Problem, where 𝑁 = 2𝑛 denotes the input length.
The condition can be equivalently stated without referring to the “non-disjoint” promise problem.
Let MKtP[𝑂(log 𝑁), 𝑁 𝑜(1) ] denote the family of the promise problems MKtP[𝑐 log 𝑁 , 𝑁 𝛼 ] for
constants 𝑐, 𝛼 > 0; here, for functions 𝑠, 𝑡 : ℕ → ℕ , MKtP[𝑠(𝑁), 𝑡(𝑁)] denotes the promise
problem of deciding whether Kt(𝑥) ≤ 𝑠(|𝑥|) or Kt(𝑥) > 𝑡(|𝑥|) on input 𝑥. Then, the following are
equivalent as well.
3. For all large 𝑁 ∈ ℕ , there exists no AC0 ◦ XOR circuit of size 𝑁 1+𝑜(1) that computes
MKtP[𝑂(log 𝑁), 𝑁 𝑜(1) ].
4. For any constant 𝑘 ∈ ℕ , for all large 𝑁 ∈ ℕ , there exists no AC0 ◦ XOR circuit of size 𝑁 𝑘 that
computes MKtP[𝑂(log 𝑁), 𝑁 𝑜(1) ].
Observe that Item 1 of Theorem 1.11 implies a strongly exponential AC0 circuit lower bound
for E (i. e., E cannot be computed by AC0 circuits of size 2𝑜(𝑛) ), which also implies that EXP ⊄ NC1
(see, e. g., [3, 58, 28]). The current best AC0 circuit lower bound for E is due to Håstad [29], who
proved that the Parity function on 𝑛 inputs cannot be computed by depth-𝑑 AC0 circuits of size
2𝑜(𝑛
1/(𝑑−1) )
. Theorem 1.11 shows that, in order to improve this state-of-the-art lower bound, it is
sufficient to prove a nearly linear AC0 ◦ XOR lower bound for the E vs SIZE(2𝑜(𝑛) ) Problem. In
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 10
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
contrast, the minimum circuit for computing the E vs SIZE(2𝑜(𝑛) ) Problem is infinity under the
standard circuit lower bound assumption that E ⊄ SIZE(2𝑜(𝑛) ).
It is instructive to compare our results with the hardness versus randomness framework.
In order to obtain a hitting set generator in the latter framework, we need to find an explicit
function that is hard for small circuits to compute. In our framework, finding an explicit hard
function corresponds to proving that the minimum circuit size for computing MCLPs is infinity
(or, in other words, proving that there exists no circuit of any size that computes MCLPs4). Our
results significantly weaken the assumption needed to obtain a hitting set generator: It suffices
to show that a nearly linear circuit cannot find the difference between an explicit function and a
hard function.
Our results can be also stated based on the case analysis. There are two cases. (1) When the
circuit lower bound that E ⊄ SIZE(2𝑜(𝑛) ) holds, the work of [44] already implies the existence of
a pseudorandom generator. (2) Even if the circuit lower bound does fail, Theorem 1.11 shows
that a very modest AC0 ◦ XOR lower bound for the E vs SIZE(2𝑜(𝑛) ) Problem (which is a disjoint
promise problem under the assumption) implies the existence of a hitting set generator. In either
case, we obtain a hitting set generator. Our results generalize the hardness versus randomness
framework in this sense.
Previously, based on the hardness versus randomness framework, it is known that E ⊄ ℭ is
equivalent to the existence of a pseudorandom generator secure against ℭ for a sufficiently large
class ℭ (see, e. g., [23]). However, in the previous approach, one needs to transform a worst-case
ℭ-circuit lower bound to an average-case ℭ-circuit lower bound; thus ℭ needs to be a sufficiently
large so that it can perform local decoding, which requires the majority gate [66]. For any circuit
class ℭ smaller than TC0 , it was not clear whether the existence of a hitting set generator secure
against ℭ is equivalent to some worst-case ℭ-circuit lower bound. Theorem 1.11 establishes the
first equivalence for the circuit class ℭ = AC0 ◦ XOR, which is smaller than TC0 [62].
Our results can be stated without the non-standard notion of promise problem, as in Items 3
and 4 of Theorem 1.11. Indeed, any promise problem in the family MKtP[𝑂(log 𝑁), 𝑁 𝑜(1) ]
asks for approximating the Kt-complexity of a given string, and it is always a disjoint promise
𝑜(𝑛)
problem. In our terminology, MKtP[𝑂(log 𝑁), 𝑁 𝑜(1) ] is equivalent to the E vs DTIME(22 )/2𝑜(𝑛)
𝑜(𝑛) 𝑜(𝑛)
Problem. Since SIZE(2𝑜(𝑛) ) ⊆ DTIME(22 )/2𝑜(𝑛) , one can observe that the E vs DTIME(22 )/2𝑜(𝑛)
Problem is reducible to the E vs SIZE(2𝑜(𝑛) ) Problem via an identity map, which explains the
implication from Item 3 to Item 2 in Theorem 1.11.
We mention that it is not hard to prove an AC0 lower bound for MKtP[𝑂(log 𝑁), 𝑁 𝑜(1) ] and
in particular for the E vs SIZE(2𝑜(𝑛) ) Problem.
Proposition B.1. For any constants 𝛼 < 1, 𝑘, 𝑑 ∈ ℕ , there exists a constant 𝑐 such that
MKtP[𝑐 log 𝑁 , 𝑁 𝛼 ] ∉ i.o.AC0𝑑 (𝑁 𝑘 ).
This can be proved by using the pseudorandom restriction method as in [37, 18, 14]. (See
Appendix B for a proof.) Extending Proposition B.1 to the case of AC0 ◦ XOR is sufficient for a
4This should be compared with the fact that any disjoint promise problem can be computed by a circuit of size
𝑂(2𝑛 /𝑛) on inputs of length 𝑛.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 11
S HUICHI H IRAHARA
breakthrough result in light of Theorem 1.11.
For any classes ℭ, 𝔇 of functions, one can define the ℭ vs 𝔇 Problem. A particularly
g0 (2𝑜(𝑛) ; 1 − 2−𝑜(𝑛) ) Problem, where 𝔇(𝑠;
interesting problem is the E vs AC e 𝛿) denotes the class of
2
functions that can be computed by a 𝔇-circuit of size 𝑠 on at least a (1 − 𝛿) fraction of inputs.
We prove that, if nearly linear-size AC0 circuits cannot distinguish an explicit function from a
function that cannot be approximated by small AC0 circuits, then a logarithmic-seed-length
hitting set generator can be obtained. (Moreover, the converse direction is easy to prove.)
Theorem 1.12. The following are equivalent.
1. For all large 𝑁 = 2𝑛 , the E vs AC
g0 (2𝑜(𝑛) ; 1 − 2−𝑜(𝑛) ) Problem cannot be decided by AC0 circuits of
2
size 𝑁 1+𝑜(1) .
2. There exists a hitting set generator 𝐺 = {𝐺 𝑛 : {0, 1} 𝑂(log 𝑛) → {0, 1} 𝑛 } 𝑛∈ℕ computable in time
𝑛 𝑂(1) and secure against linear-size AC0 circuits.
3. MKtP[𝑂(log 𝑁), 𝑁 − 1] ∉ i.o.AC0 (𝑁 1+𝛽 ) for some constant 𝛽 > 0.
4. MKtP[𝑂(log 𝑁), 𝑁 − 1] ∉ i.o.AC0 (𝑁 𝑘 ) for any constant 𝑘.
An interesting aspect of Theorem 1.12 is its self-referential nature; intuitively, Item 1 means
that AC0 circuits cannot analyze AC0 circuits itself. Note that self-reference is crucial for proving,
e. g., time hierarchy theorems for uniform computational models. Theorem 1.12 provides an
analogue in a non-uniform circuit model.
Why do we consider “non-disjoint” promise problems, despite the fact that Theorems 1.11
and 1.12 can be stated without referring to the non-standard notion? A couple of remarks
are in order. First, Theorem 1.11 is obtained by viewing (a variant of) the black-box PRG
construction of Impagliazzo and Wigderson [44] from a meta-computational perspective; thus,
it is natural to state Theorem 1.11 as a connection between the existence of a hitting set
generator and a lower bound for the E vs SIZE(2𝑜(𝑛) ) Problem. Second, an identity map reduces
MKtP[𝑂(log 𝑁), 𝑁 𝑜(1) ] to the E vs SIZE(2𝑜(𝑛) ) Problem, and thus it is easier to prove a lower
bound for the latter problem. Third, the known worst-case-and-average-case equivalence
between E ⊆ SIZE(2𝑜(𝑛) ) and E ⊆ SIZE (2𝑜(𝑛) ; 1 − 2−𝑜(𝑛) ) [68] can be naturally regarded as a
2
reduction from the E vs SIZE(2𝑜(𝑛) ) Problem to the E vs SIZE
(2𝑜(𝑛) ; 1 − 2−𝑜(𝑛) ) Problem. Indeed,
2
Theorem 1.12 is proved by viewing the Nisan–Wigderson pseudorandom generator from a
meta-computational perspective, and then Theorem 1.12 is translated into Theorem 1.11 by
using the worst-case-and-average-case equivalence. Lastly and most importantly, in the other
settings, the non-disjointness itself provides new consequences, such as Corollaries 1.5 and 1.16.
We also present a potential approach for resolving the RL = L question. Here, RL is the
complexity class of languages that can be solved by a one-sided-error randomized 𝑂(log 𝑛)-space
Turing machine that reads its random tape only once. A canonical approach for proving RL = L
is to construct a log-space-computable hitting set generator of seed length 𝑂(log 𝑛) secure
against 𝑂(𝑛)-size read-once branching programs. State-of-the-art results are the pseudorandom
generator of seed length 𝑂(log2 𝑛) by Nisan [55] for read-once (known-order) oblivious branching
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 12
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
programs, and the pseudorandom generator of seed length 𝑂(log3 𝑛) by Forbes and Kelley [22]
for read-once unknown-order oblivious branching programs.5
We show that a hitting set generator of seed length 𝑂(log 𝑛) can be constructed if nearly
linear-size read-once co-nondeterministic branching programs cannot distinguish linear-space-
computable functions from hard functions.
Theorem 1.13. Suppose that, for some constants 𝛽, 𝛿 ∈ (0, 1/2), the DSPACE(𝑛) vs SIZE (2𝑜(𝑛) ; 𝛿)
Problem cannot be computed by read-once co-nondeterministic branching programs of size 𝑁 1+𝛽 for
all large input lengths 𝑁 = 2𝑛 . Then there exists a hitting set generator 𝐺 = {𝐺 𝑛 : {0, 1} 𝑂(log 𝑛)
→ {0, 1} 𝑛 } 𝑛∈ℕ computable in 𝑂(log 𝑛) space and secure against linear-size read-once branching
programs (and, in particular, RL = L follows; moreover, BPL = L holds6).
Theorem 1.13 can be compared with a result of Klivans and van Melkebeek [48]. Based on
the hardness versus randomness framework, they showed BPL = L under the assumption that
DSPACE(𝑛) requires circuits of size 2Ω(𝑛) . Under the same assumption, by using a worst-case-
to-average-case reduction for DSPACE(𝑛), it can be shown that the DSPACE(𝑛) vs SIZE (2𝑜(𝑛) ; 𝛿)
Problem is non-disjoint for any constant 𝛿 < 1/2 (see Proposition 4.11). In this case, the
minimum size of a co-nondeterministic branching program for computing the MCLP is infinity;
thus, Theorem 1.13 generalizes the result of [48].
It should be noted that the limits of the computational power of read-once non-deterministic
branching programs are “well understood.” For example, Borodin, Razborov, and Smolensky [9]
presented an explicit function that cannot be computed by any read-𝑘-times nondeterministic
branching program of size 2𝑜(𝑛) for any constant 𝑘. Theorem 1.13 shows that, in order to resolve
BPL = L, it suffices to similarly analyze the read-once co-nondeterministic branching program
size for computing the MCLP. This approach could be useful; by using the Nechiporuck method,
it can be shown that neither nondeterministic nor co-nondeterministic branching programs of
size 𝑜(𝑁 1.5 /log 𝑁) can compute MKtP [17], which is a much more general lower bound than
read-𝑘-times nondeterministic branching programs.
We also mention that a partial converse of Theorem 1.13 is easy to prove: If there exists a
log-space-computable hitting set generator secure against linear-size read-once nondeterministic
branching programs, then the DSPACE(𝑛) vs SIZE (2𝑜(𝑛) ; 𝛿) Problem cannot be computed by a
read-once co-nondeterministic branching programs of size 𝑁 𝑘 , where 𝑁 = 2𝑛 and 𝛿 < 1/2 is an
arbitrary constant. More generally, any results showing the existence of a hitting set generator
secure against ℭ must entail a coℭ-lower bound for MCLPs (see Proposition 4.22).
1.3.2 Non-trivial derandomization and lower bounds for MKtP
Our proof techniques can be also applied to uniform algorithms. We consider the question
of whether one-sided-error uniform algorithms can be non-trivially derandomized in time
5In the area of unconditional derandomization of space-bounded randomized algorithms, it is common to assume
that a branching program is oblivious and reads the input in the fixed order. Here, we do not assume these properties.
6This is because of a recent result of Cheng and Hoza [16], which shows BPL = L from the existence of a hitting
set generator.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 13
S HUICHI H IRAHARA
√
2𝑛−𝜔( 𝑛 log 𝑛) . We say that an algorithm 𝐴 is a derandomization algorithm for DTIME(𝑡(𝑛)) if, for
any machine 𝑀 running in time 𝑡(𝑛), 𝐴 takes 1𝑛 and a description of 𝑀 as input and outputs
𝑦 ∈ {0, 1} 𝑛 such that 𝑀(𝑦) = 1 for infinitely many 𝑛 ∈ ℕ such that Pr𝑥∼{0,1}𝑛 [𝑀(𝑥) = 1] ≥ 12 .
Unlike the standard setting of a derandomization algorithm for non-uniform computational
models, the description length of 𝑀 is at most a constant independent of input length 𝑛; thus,
our notion of derandomization algorithm is essentially equivalent to the existence of a hitting
set generator secure against DTIME(𝑡(𝑛)). Applying our proof techniques to this setting, we
establish the following equivalence between the existence of a derandomization algorithm for
uniform algorithms and a lower bound for approximating Kt complexity.
Theorem 1.14 (informal; see Theorem 5.5). For any constant 0 < 𝜖 < 1, the following are equivalent:
√ √
1. There exists a derandomization algorithm for DTIME(2𝑂( 𝑁 log 𝑁) ) that runs in time 2𝑁−𝜔( 𝑁 log 𝑁) .
√ √
2. MKtP[𝑁 − 𝜔( 𝑁 log 𝑁), 𝑁 − 1] ∉ DTIME(2𝑂( 𝑁 log 𝑁) ).
√ √
𝜖
3. MKtP[𝑁 𝜖 , 𝑁 𝜖 + 𝜔( 𝑁 𝜖 log 𝑁)] ∉ DTIME(2𝑂( 𝑁 log 𝑁) ).
Usually, the time complexity is measured with respect to √
the input size. Our result, however,
suggests that the time complexity of MKtP[𝑠(𝑁), 𝑠(𝑁) + 𝜔( 𝑁 log 𝑁)] is well captured by the
size parameter 𝑠(𝑁) rather than the input size 𝑁: Indeed, Theorem 1.14 implies that
√ √
𝜖
MKtP[𝑁 𝜖 , 𝑁 𝜖 + 𝜔( 𝑁 𝜖 log 𝑁)] ∈ DTIME(2𝑂( 𝑁 log 𝑁) )
is equivalent to
√ √
𝛿
MKtP[𝑁 𝛿 , 𝑁 𝛿 + 𝜔( 𝑁 𝛿 log 𝑁)] ∈ DTIME(2𝑂( 𝑁 log 𝑁) )
for any 0 < 𝜖, 𝛿 < 1.
Theorem 1.14 highlights the importance of a lower bound for MKtP. In fact, it is a long-
standing open question whether MKtP ∉ P, despite the fact that MKtP is an EXP-complete
problem under non-uniform reductions [2]. Towards resolving this open question, we present
several results that might be useful. We show that some “non-disjoint” promise problem can be
solved under the assumption that MKtP ∈ P.
√
Theorem 1.15. Assume that MKtP ∈ P. Then, there exists a 2𝑂( 𝑛) -time algorithm that solves the
e
Kt vs K𝑡 Problem, which is defined as follows: Given a string
√ 𝑥 ∈ {0, 1}∗ of length 𝑛 and a parameter
𝑠 ∈ ℕ , distinguish whether Kt(𝑥) ≤ 𝑠 or K (𝑥) ≥ 𝑠 + 𝑂( 𝑠 log 𝑛 + log2 𝑛), where 𝑡 := 𝑛 log 𝑛 .
𝑡
Using the disjointness of the Kt vs K𝑡 Problem and setting 𝑠 := Kt(𝑥), we obtain
Corollary 1.16. If MKtP ∈ P, then K𝑡 (𝑥) ≤ Kt(𝑥) + 𝑂( Kt(𝑥) log 𝑛 + log2 𝑛) for any 𝑥 ∈ {0, 1} 𝑛 ,
p
where 𝑡 := 𝑛 log 𝑛 .
Since Kt(𝑥) ≤ K𝑡 (𝑥) + 𝑂(log2 𝑛) holds for 𝑡 := 𝑛 log 𝑛 unconditionally, Corollary 1.16 shows
√
that Kt(𝑥) and K𝑡 (𝑥) are equal up to an additive term of 𝑂( e 𝑛) under the assumption that
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 14
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
MKtP ∈ P. In particular, in order to resolve MKtP ∉ P, it suffices to prove that K𝑡 (𝑥) cannot be
√
approximated within an additive error 𝑂( e 𝑛) in polynomial time. It was shown in [35] that
there is no polynomial-time algorithm that computes K𝑡 (𝑥) exactly on input 𝑥. The large additive
√
error term 𝑂(e 𝑛) prevents us from combining the lower bound proof technique of [35] and
Corollary 1.16.
1.3.3 Related work: Minimum Circuit Size Problem
The definitions of MCLPs are inspired by the Minimum Circuit Size Problem (MCSP). While
the history of MCSP is said to date back to as early as 1950s [69], its importance was not
widely recognized until Kabanets and Cai [45] named the problem as MCSP and investigated it
based on the natural proof framework of Razborov and Rudich [63]. The task of MCSP is to
decide whether there exists a size-𝑠 circuit that computes 𝑓 , given the truth table of a function
𝑓 : {0, 1} 𝑛 → {0, 1} and a size parameter 𝑠 ∈ ℕ . It turned out that MCSP is one of the central
computational problems in relation to wide research areas of complexity theory, including
circuit lower bounds [63, 58], learning theory [13], cryptography [63, 2, 4, 65], and average-case
complexity [32].
It has been recognized that MCSP lacks one desirable mathematical property — monotonicity
with respect to an underlying computational model. MCSP can be defined for any circuit classes
ℭ; for example, ℭ-MCSP stands for a version of MCSP where the task is to find the minimum
ℭ-circuit size; MCSP𝐴 stands for the minimum 𝐴-oracle circuit size problem. We are tempted to
conjecture that, as a computational model becomes stronger, the corresponding minimization
problem becomes harder; e. g., MCSP𝐴 should be harder than MCSP for any oracle 𝐴. However,
this is not the case — Hirahara and Watanabe [38] showed that there exists an oracle 𝐴 such that
𝑝
MCSP 6 ≤𝑇 MCSP𝐴 unless MCSP ∈ P. Moreover, DNF-MCSP [52, 3] and (DNF ◦ XOR)-MCSP
[36] are known to be NP-complete, whereas NP-completeness of MCSP is a long-standing open
question.
Why does the monotonicity of MCSP fail? For two circuit classes ℭ and 𝔇, define the ℭ vs 𝔇
Problem to be the promise problem of distinguishing whether 𝑓 has a ℭ-circuit of size 𝑠 or 𝑓
does not have a 𝔇-circuit of size 𝑠, given the truth table of a function 𝑓 : {0, 1} 𝑛 → {0, 1} and a
size parameter 𝑠. Then, ℭ-MCSP can be regarded as a special case of the ℭ vs 𝔇 Problem where
ℭ = 𝔇. It is easy to observe that the ℭ vs 𝔇 Problem is reducible to the ℭ0 vs 𝔇0 Problem via an
identity map if ℭ ⊆ ℭ0 and 𝔇 ⊇ 𝔇0; thus, MCLPs have monotonicity properties in this sense. In
contrast, the monotonicity property of MCLPs fails when ℭ = 𝔇 ⊆ ℭ0 = 𝔇0, which corresponds
to the case of MCSP.
In an attempt to remedy the monotonicity issue, Hirahara and Santhanam [37] observed that
average-case complexity of MCSP is monotone increasing. Carmosino, Impagliazzo, Kabanets,
and Kolokolova [13] implicitly showed that the complexity of MCSP is monotone increasing
under non-black-box reductions.
In contrast, MCLPs incorporate the monotonicity property in the definition itself, which
makes a mathematical theory cleaner. For example, recall that it can be shown that E ⊄ SIZE(2𝑜(𝑛) )
if and only if E ⊄ SIZE (2𝑜(𝑛) ; 1 − 2−𝑜(𝑛) ) by using error-correcting codes [68]. Viewing this
2
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 15
S HUICHI H IRAHARA
equivalence from a meta-computational perspective, it can be interpreted as an efficient
reduction from the E vs SIZE(2𝑜(𝑛) ) Problem to the E vs SIZE
(2𝑜(𝑛) ; 1 − 2−𝑜(𝑛) ) Problem (see
2
Theorem 4.27). A similar reduction was presented for MCSP under the assumption that
EXP ⊆ P/poly [14]; finding such a reduction for MCSP requires certain creativity, whereas
working with the definition of MCLPs makes it trivial to find the reduction.
1.3.4 Related work: Hardness Magnification
A recent line of work [58, 57, 53, 15, 14] exhibit surprising phenomena, which are termed as
“hardness magnification phenomena.” Oliveira, Santhanam, and Pich [58, 57] showed that very
weak lower bounds for MCSP and related problems are sufficient for resolving long-standing
open questions about circuit lower bounds, such as EXP ⊄ NC1 . An interesting aspect of
hardness magnification phenomena is that, as argued in [5, 58], the argument does not seem to
be subject to the natural proof barrier of Razborov and Rudich [63], which is one of the major
obstacles of complexity theory. Our results can be seen as a new interpretation of hardness
magnification phenomena from the perspective of a construction of a hitting set generator.
It is worthwhile to point out that our reductions have very similar structures to hardness
magnification phenomena. For example, it was shown in [58, 57] that, for a parameter
𝑠 = 𝑠(𝑁), the problem MKtP[𝑠, 𝑠 + 𝑂(log 𝑁)] can be solved by an AND𝑂(𝑁) ◦ 𝐷poly(𝑠) ◦ XOR circuit,
where 𝐷poly(𝑠) is an oracle gate computable in EXP that takes an input of length poly(𝑠). This
reduction shows that EXP ⊆ P/poly implies MKtP[𝑠, 𝑠 + 𝑂(log 𝑁)] ∈ SIZE(𝑁 · poly(𝑠)). Taking
its contrapositive, it can be interpreted as a hardness magnification phenomenon: for 𝑠(𝑁) 𝑁,
a (seemingly) weak lower bound MKtP[𝑠, 𝑠 + 𝑂(log 𝑁)] ∉ SIZE(𝑁 · poly(𝑠)) can be “hardness
magnified” to a strong circuit lower bound EXP ⊄ P/poly.
Theorem 1.11 has exactly the same structure with the reduction mentioned above. Given
a circuit 𝐷𝑁 𝑜(1) that avoids a hitting set generator, we construct a nearly linear-size AND𝑂(𝑁) ◦
𝐷𝑁 𝑜(1) ◦ XOR circuit that computes the E vs SIZE(2𝑜(𝑛) ) Problem. Thus, our reductions are as
efficient as the reductions presented in the line of work of hardness magnification phenomena.
More importantly, our results significantly strengthen the consequences of hardness magni-
fication: Not only circuit lower bounds, but also hitting set generators can be obtained. This is
especially significant for the case of read-once branching programs. Since there is already an
exponential size lower bound for read-once branching programs [9], it does not make sense
to try to hardness-magnify a lower bound for read-once branching programs. In contrast, our
results (Theorem 1.13) indicate that a nearly linear size lower bound for co-nondeterministic
read-once branching programs is enough for resolving BPL = L.
An intriguing question about hardness magnification is this: By using hardness magni-
fication phenomena, can we prove any new consequences, such as circuit lower bounds or
derandomization? Theorem 1.13 adds a new computational model, i. e., co-nondeterministic
read-once branching programs, for exploring this question.
Chen, Hirahara, Oliveira, Pich, Rajgopal, and Santhanam [14] proposed a barrier for the
question, termed as a “locality barrier.” Briefly speaking, the idea there is to regard hardness
magnification phenomena as a (black-box) reduction to oracles with small fan-in, and then to
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 16
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
show that most circuit lower bound proofs can be extended to rule out such a reduction; thus,
such a circuit lower bound proof technique cannot be combined with hardness magnification
phenomena. A salient feature of our reductions is that our reductions are non-black-box in
the sense that we exploit the efficiency of oracles; the non-black-box property appears in the
definition of No instances of the ℭ vs 𝔇 Problem. In light of this, our results provide a potential
approach for bypassing the locality barrier: Try to develop a circuit lower bound proof technique
that crucially exploits the structure of the No instances of the ℭ vs 𝔇 Problem. The existing
circuit lower bound proof techniques for MCSP and related problems fail to exploit such a
structure.
1.4 Proof techniques: Meta-computational view of PRG constructions
All of our results are given by a single principle — that views any black-box pseudorandom
generator construction from a meta-computational perspective. The differences among our
theorems simply originate from the fact that we use a different black-box pseudorandom
generator construction. The underlying principle is this:
Any black-box construction of a pseudorandom generator 𝐺 𝑓 based on a hard
function 𝑓 ∉ ℛ gives rise to a non-black-box security reduction for a hitting set
generator based on the hardness of a non-disjoint promise problem (e. g., the E vs ℛ
Problem).
For the purpose of exposition, we take a specific PRG construction of Impagliazzo and
Wigderson [44], and prove a connection between the PRG construction and the E vs SIZE(2𝑜(𝑛) )
Problem. Specifically, in this section, we present a self-contained proof of the following result.
Theorem 1.17. There exists a universal constant 𝛽 such that the following are equivalent.
1. The E vs SIZE(2𝑜(𝑛) ) Problem cannot be solved by a circuit of size 𝑁 𝛽 on inputs of length 𝑁 = 2𝑛
for all large 𝑁.
2. There exists a hitting set generator 𝐻 = {𝐻𝑚 : {0, 1} 𝑂(log 𝑚) → {0, 1} 𝑚 } 𝑚∈ℕ computable in time
𝑚 𝑂(1) and secure against linear-size circuits.
The implication from Item 2 to Item 1 is by now a standard fact in the literature of MCSP
and Kolmogorov complexity [63, 2]. The implication from Item 1 to Item 2 is shown by applying
our principle to the following black-box pseudorandom generator construction of [44].
Lemma 1.18 (Impagliazzo and Wigderson [44]). There is a constant 𝛽 such that, for any constant
𝛼 > 0, there exist a constant 0 < 𝛼0 < 1/2 and a “black-box pseudorandom generator construction”
𝛼0 𝑛
𝐺 𝑓 : {0, 1} 𝑂(𝑛) → {0, 1}2 that takes a function 𝑓 : {0, 1} 𝑛 → {0, 1} for any 𝑛 ∈ ℕ and satisfies the
following.
Explicitness 𝐺 𝑓 (𝑧) is computable in time 2𝑂(𝑛) given the truth table of 𝑓 and a seed 𝑧.
Constructivity For every fixed seed 𝑧 ∈ {0, 1} 𝑂(𝑛) , there is a circuit 𝐶 𝑧 of size 2(𝛽−2)𝑛 that takes as
input the 2𝑛 -bit truth table of a function 𝑓 and computes 𝐺 𝑓 (𝑧).
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 17
S HUICHI H IRAHARA
𝛼0 𝑛
Security For every function 𝐷 : {0, 1}2 → {0, 1} that 14 -distinguishes7 the output distribution of
𝐺 𝑓 (-) from the uniform distribution, then 𝑓 ∈ SIZE𝐷 (2(𝛼−𝛼 )𝑛 ).
0
Here, by “black-box”,8 we mean that the security of the PRG is proved by a (black-box)
reduction, i. e., the security reduction works for every function 𝐷; otherwise, the reduction is
called non-black-box (e. g., in the case when the reduction works only if the oracle is efficient).
This is in the same spirit with the non-black-box reduction of [32], which overcomes the black-
box reduction barrier of Bogdanov and Trevisan [8]. We explain below how a black-box PRG
construction gives rise to a non-black-box security reduction of some hitting set generator.
Proof of Theorem 1.17. (Item 1 ⇒ 2) The goal is to construct some secure hitting set generator
𝐻 = {𝐻𝑚 : {0, 1} 𝑐0 log 𝑚 → {0, 1} 𝑚 } 𝑚∈ℕ for some constant 𝑐0 . As a choice of 𝐻, we simply take
a “universal” hitting set generator: Let 𝑈 be a universal Turing machine, i. e., a machine that
simulates every Turing machine efficiently. Then we define 𝐻𝑚 (𝑧) to be the output of 𝑈 on
input 𝑧 if 𝑈 outputs a string of length 𝑚 in 2|𝑧| steps, where 𝑧 ∈ {0, 1} 𝑐0 log 𝑚 . The important
property of 𝐻𝑚 is that every string 𝑥 ∈ {0, 1} 𝑚 with Kt(𝑥) ≤ 𝑐0 log 𝑚 is contained in the image
of 𝐻𝑚 . (The choice of 𝐻 is universal, in the sense that the existence of some exponential-time
computable HSG implies that 𝐻 is also secure.)
The strategy for proving the security of a hitting set generator 𝐻 is to regard a function
𝑓 : {0, 1} 𝑛 → {0, 1} as an input of the E vs SIZE(2𝑜(𝑛) ) Problem, and to view the black-box PRG
construction 𝐺 𝑓 as a (non-black-box) reduction that proves the security of 𝐻.
We claim that 𝐻 is a hitting set generator secure against linear-size circuits, under the
assumption that the E vs SIZE(2𝑜(𝑛) ) Problem cannot be solved by small circuits. To this end, we
present a non-black-box reduction 𝑅 (-) from the task of solving the E vs SIZE(2𝑜(𝑛) ) Problem to
the task of “avoiding” 𝐻. That is, we prove the contrapositive of Item 1 ⇒ 2: Assume that 𝐻 is
not secure (for every constant 𝑐0 , which decides the seed length of 𝐻). Then, for infinitely many
𝑚 ∈ ℕ , there exists a linear-size circuit 𝐷 that avoids 𝐻𝑚 , i. e., every string in the image of 𝐻𝑚 is
rejected by 𝐷 whereas 𝐷 accepts at least a half of all the 𝑚-bit inputs. We claim that there exists
a small oracle circuit 𝑅 𝐷 that solves the E vs SIZE(2𝑜(𝑛) ) Problem. The randomized circuit 𝑅 𝐷 is
extremely simple:
A randomized algorithm 𝑅 𝐷 for solving the E vs SIZE(2𝑜(𝑛) ) Problem with 𝐷 oracle
Given 𝑓 as an input, pick a random seed 𝑧 of 𝐺 𝑓 , and accept if and only if 𝐷(𝐺 𝑓 (𝑧)) = 0.
More formally, recall that the E vs SIZE(2𝑜(𝑛) ) Problem is defined as the family of promise
problems Π𝑐,𝛼 = (ΠYes (2𝑐𝑛 ), ΠNo (2𝛼𝑛 )) for every 𝑐, 𝛼 > 0 as in Definition 1.10. We need to prove
that, for any constants 𝑐, 𝛼 > 0, for infinitely many 𝑛 ∈ ℕ , there exists a randomized circuit 𝑅 𝐷
that solves Π𝑐,𝛼 on inputs of length 𝑁 = 2𝑛 . We take 𝛼0 of Lemma 1.18 (depending on 𝑐, 𝛼), and
choose 𝑛 ∈ ℕ so that 𝑚 = 2𝛼 𝑛 .9
0
7That is, Pr𝑧 𝐷(𝐺 𝑓 (𝑧)) = 1 − Pr𝑤 [𝐷(𝑤) = 1] ≥ 1/4; see Section 2 for the definition of PRG.
8In the taxonomy of [64], 𝐺(-) is fully black-box in the sense that the construction from 𝑓 to 𝐺 𝑓 also works for every
function 𝑓 .
9More precisely, we consider infinitely many 𝑚 such that 𝐷 avoids 𝐻𝑚 ; then, setting 𝑛 := (log 𝑚)/𝛼0 , we prove
that the reduction 𝑅 𝐷 solves Π𝑐,𝛼 on inputs of length 𝑛.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 18
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
The correctness of the reduction 𝑅 𝐷 can be proved as follows. Assume that 𝑓 is a Yes
instance of the promise problem Π𝑐,𝛼 ; this means that Kt( 𝑓 ) ≤ log 2𝑐𝑛 = 𝑐𝑛. It follows
from the explicitness of 𝐺 𝑓 (Lemma 1.18) that we can take a large constant 𝑐0 such that
Kt(𝐺 𝑓 (𝑧)) ≤ 𝑐 0 𝛼0 𝑛 = 𝑐0 log 𝑚 for every seed 𝑧 ∈ {0, 1} 𝑂(𝑛) . By the definition of the universal
hitting set generator 𝐻𝑚 , one can observe that 𝐺 𝑓 (𝑧) ∈ {0, 1} 𝑚 is in the image of 𝐻𝑚 (for infinitely
many 𝑚); therefore, 𝐺 𝑓 (𝑧) is rejected by 𝐷 for every 𝑧, and hence the reduction 𝑅 𝐷 accepts 𝑓
with probability 1.
Conversely, we prove that any No instance 𝑓 of Π𝑐,𝛼 is rejected by the reduction 𝑅 𝐷
with probability at least 14 . Intuitively, this is because of the fact that if 𝑓 is a hard function,
then 𝐷 cannot distinguish 𝐺 𝑓 (-) from the uniform distribution. More formally, we prove the
contrapositive. Assume that 𝑅 𝐷 rejects 𝐺 𝑓 (𝑧) with probability at most 14 . This means that
1
Pr[𝐷(𝐺 𝑓 (𝑧)) = 1] ≤ .
𝑧 4
On the other hand, since 𝐷 avoids 𝐻𝑚 , we have Pr𝑤 [𝐷(𝑤) = 1] ≥ 12 . Therefore,
1
Pr[𝐷(𝑤) = 1] − Pr[𝐷(𝐺 𝑓 (𝑧)) = 1] ≥ ,
𝑤 𝑧 4
which means that ¬𝐷 14 -distinguishes 𝐺 𝑓 from the uniform distribution. By using the black-box
security property of 𝐺 𝑓 (Lemma 1.18), we obtain that 𝑓 ∈ SIZE𝐷 (2(𝛼−𝛼 )𝑛 ). Since 𝐷 is a linear-size
0
circuit (i. e., of size 𝑚 = 2𝛼 𝑛 ), we conclude that 𝑓 ∈ SIZE(2𝛼𝑛 ), which means that 𝑓 is not a No
0
instance of the promise problem Π𝑐,𝛼 . Note here that we rely on the efficiency of 𝐷, which
makes the security proof of the HSG 𝐻 non-black-box.
To summarize, the promise problem Π𝑐,𝛼 can be solved by the randomized circuit 𝑅 𝐷 of size
𝑁 𝛽−2 + 2𝛼 𝑛 ≤ 𝑁 𝛽−1.5 , where the size bound follows from the constructivity of 𝐺 𝑓 (Lemma 1.18).
0
By using the standard trick of Adleman [1], the randomized circuit 𝑅 𝐷 of size 𝑁 𝛽−1.5 can be
converted to a deterministic circuit of size 𝑂(𝑁 𝛽−0.5 ) (by amplifying the success probability and
fixing a good random coin flip). We conclude that the E vs SIZE(2𝑜(𝑛) ) Problem can be solved by
a circuit of size 𝑁 𝛽 .
(Item 2 ⇒ 1) Conversely, if there exists a hitting set generator 𝐻 secure against linear-size
circuits, then the E vs SIZE(2𝑜(𝑛) ) Problem cannot be solved by circuits of size 𝑁 𝛽 for any
0
constant 𝛽0. Indeed, we can prove the contrapositive (roughly) as follows. Given a circuit 𝐷
that solves the E vs SIZE(2𝑜(𝑛) ) Problem, we claim that the circuit ¬𝐷 avoids 𝐻. On one hand,
any string 𝑥 in the image of 𝐻 satisfies that Kt(𝑥) = 𝑂(log |𝑥|); therefore, 𝑥 is a Yes instance of
the E vs SIZE(2𝑜(𝑛) ) Problem, and hence rejected by ¬𝐷. On the other hand, a string 𝑥 chosen
uniformly at random has circuit complexity at least 2𝛼𝑛 with high probability for any constant
𝛼 < 1; therefore, ¬𝐷 accepts most inputs. (See Proposition 4.22 for a formal proof.)
Note that the proof above shows a generic connection between a black-box pseudorandom
generator construction and a “non-disjoint” promise problem. The efficiency of the security
reduction depends on the choice of a black-box PRG construction. For example, Theorem 1.11
is proved by giving an efficient implementation of the black-box PRG construction 𝐺 (-) of [44]
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 19
S HUICHI H IRAHARA
such that 𝐺 𝑓 (𝑧) is computable by one layer of XOR gates for every fixed seed 𝑧. In the rest
of this paper, we present some of the instantiations of the proof ideas above based on several
specific constructions of PRGs; however, we emphasize that our reductions are not limited to
those specific instantiations, and new black-box PRG constructions can lead to a more efficient
reduction and a “non-disjoint” promise problem that is easy to analyze.
1.5 Perspective: Meta-computational view of complexity theory
More broadly, we propose to view complexity theory from a meta-computational perspective.
In order to explain the view, it is helpful to regard an algorithm that tries to solve MCLPs
as a malicious prover that tries to falsify a circuit lower bound. To be more specific, consider
the E vs SIZE(2𝑜(𝑛) ) Problem. As we explained earlier, the existence of any algorithm (of any
complexity) that solves the E vs SIZE(2𝑜(𝑛) ) Problem implies that E ⊆ SIZE(2𝑜(𝑛) ), and moreover
the converse direction is also true (for non-uniform algorithms). In this sense, any algorithm
that solves an MCLP can be regarded as an adversary that falsifies circuit lower bounds such as
E ⊄ SIZE(2𝑜(𝑛) ).
Complexity theory can be regarded as a game between us (i. e., complexity theorists, who
try to prove circuit lower bounds) and provers (i. e., algorithms that solve MCLPs). We lose the
game if some prover can solve MCLPs (and hence circuit lower bounds fail). We win the game
if we find an explicit function whose circuit complexity is high. This is equivalent to finding
a witness for the non-disjointness of the E vs SIZE(2𝑜(𝑛) ) Problem, and thus it is equivalent to
showing that there exists no prover that can solve the MCLP. In other words, prior to our work,
we implicitly tried to fight against every prover without any restriction on efficiency.
What we showed in this work is that we do not have to fight against every non-efficient prover.
Instead, in order to obtain a circuit lower bound (which is implied by the existence of a hitting
set generator), it suffices to show that no efficient algorithms such as nearly linear-size AC0 ◦ XOR
circuits can find the difference between explicit functions and hard functions. In principle, it
should be easier to prove a nearly linear circuit size lower bound for some problem when we
believe that the problem does not admit any algorithm (because of the non-disjointness). While
we have not found any existing method for proving such a lower bound that is sufficient for
breakthrough results, we believe that this is simply because of the fact that MCLPs were not
investigated explicitly. We leave as an important open question to develop a proof technique to
analyze MCLPs.
2 Preliminaries
2.1 Notation
For a Boolean function 𝑓 : {0, 1} 𝑛 → {0, 1}, we denote by tt( 𝑓 ) the truth table of 𝑓 , i. e.,
the concatenation of 𝑓 (𝑥) for all 𝑥 ∈ {0, 1} 𝑛 in the lexicographical order. We often identify
𝑛
𝑓 : {0, 1} 𝑛 → {0, 1} with tt( 𝑓 ) ∈ {0, 1}2 . We denote by size( 𝑓 ) the minimum circuit size for
computing the Boolean function 𝑓 : {0, 1} 𝑛 → {0, 1}. For a parameter 𝛿, we denote by size(
g 𝑓 ; 𝛿)
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 20
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
the minimum size of a circuit 𝐶 such that 𝑓 (𝑥) = 𝐶(𝑥) on at least a (1 − 𝛿) fraction of the 𝑛-bit
inputs 𝑥.
For a function 𝑓 : {0, 1} 𝑛 → {0, 1} and an integer 𝑘 ∈ ℕ , we denote by 𝑓 𝑘 : ({0, 1} 𝑛 ) 𝑘 → {0, 1} 𝑘
the direct product of 𝑓 . We denote by 𝑓 ⊕𝑘 : ({0, 1} 𝑛 ) 𝑘 → {0, 1} the function ⊕ 𝑘 ◦ 𝑓 𝑘 , where ⊕ 𝑘 is
the parity function on 𝑘-bit inputs.
2.2 Pseudorandomness
Let 𝐺 : {0, 1} 𝑑 → {0, 1} 𝑚 and 𝐷 : {0, 1} 𝑚 → {0, 1} be functions. For an 𝜖 > 0, we say that 𝐷
𝜖-distinguishes the output distribution of 𝐺(-) from the uniform distribution if
Pr [𝐷(𝐺(𝑧)) = 1] − Pr [𝐷(𝑤) = 1] ≥ 𝜖
𝑧∼{0,1} 𝑑 𝑤∼{0,1} 𝑚
In this case, we refer 𝐷 as an 𝜖-distinguisher for 𝐺. Conversely, 𝐺 is said to 𝜖-fool 𝐷 if 𝐷 is not
an 𝜖-distinguisher for 𝐺. Similarly, we say that 𝐷 𝜖-avoids 𝐺 if Pr𝑤∼{0,1}𝑚 [𝐷(𝑤) = 1] ≥ 𝜖 and
𝐷(𝐺(𝑧)) = 0 for every 𝑧 ∈ {0, 1} 𝑑 . By default, we assume that 𝜖 := 12 .
For a circuit class ℭ and functions 𝑠 : ℕ → ℕ and 𝜖 : ℕ → [0, 1], a family of functions
𝐺 = {𝐺 : {0, 1} 𝑠(𝑛) → {0, 1} 𝑛 } 𝑛∈ℕ is said to be a pseudorandom generator that 𝜖-fools ℭ if, for all
large 𝑛 ∈ ℕ and any circuit 𝐶 ∈ ℭ of 𝑛 inputs, 𝐺 𝜖(𝑛)-fools 𝐶. We say that 𝐺 is a hitting set
generator secure against ℭ if for all large 𝑛 ∈ ℕ , there is no circuit 𝐷 ∈ ℭ on 𝑛 inputs that avoids
𝐺𝑛 .
2.3 Circuits
We measure circuit size by the number of gates (except for the input gates). For a circuit type
ℭ and 𝑠 : ℕ → ℕ and 𝛿 ∈ [0, 1], we denote by e ℭ(𝑠; 𝛿) the class of functions 𝑓 : {0, 1} 𝑛 → {0, 1}
such that there exists a circuit of size 𝑠(𝑛) such that Pr𝑥∼{0,1}𝑛 [ 𝑓 (𝑥) = 𝐶(𝑥)] ≥ 1 − 𝛿. We define
ℭ(𝑠) := e
ℭ(𝑠; 0). For the standard circuit class, we use the notation SIZE (𝑠; 𝛿) and SIZE(𝑠).
2.4 Time-bounded kolmogorov complexity
We fix an efficient universal Turing machine 𝑈. Time-bounded Kolmogorov complexity is
defined as follows.
Definition 2.1 (Time-bounded Kolmogorov Complexity). The time-𝑡 𝐴-oracle Kolmogorov
complexity of a string 𝑥 ∈ {0, 1}∗ is defined as
K𝑡,𝐴 (𝑥) := min{ |𝑑| | 𝑈 𝐴 outputs 𝑥 in 𝑡 steps on input 𝑑 ∈ {0, 1}∗ },
where 𝐴 is an oracle and 𝑡 ∈ ℕ .
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 21
S HUICHI H IRAHARA
3 Meta-computational view of cryptographic PRG constructions
In this section, we apply the meta-computational principle to cryptographic pseudorandom
generator constructions. The worst-case-to-average-case reduction for Gap(KSAT vs K) is given
in Section 3.1. We view the pseudorandom generator construction of Håstad, Impagliazzo,
Levin, and Luby [30] from a meta-computational perspective in Section 3.2.
3.1 Gap(KSAT vs K)
We present a proof of the following result.
Reminder of Theorem 1.4. Let 𝐴 be any oracle. If DistNP𝐴 ⊆ AvgP, then Gap(K𝐴 vs K) ∈ P.
At the core of the proof of Theorem 1.4 is to use a black-box PRG construction whose advice
complexity is small. Following [35], we observe that a 𝑘-wise direct product generator, which is
one of the simplest constructions of pseudorandom generators, has small advice complexity.
Theorem 3.1 (𝑘-wise direct product generator [35]). For any parameters 𝑛, 𝑘 ∈ ℕ and 𝜖 > 0 with
𝑘 ≤ 2𝑛, there exists a “black-box pseudorandom generator construction” (DP 𝑘 , 𝐴(-) , 𝑅(-) ) satisfying the
following.
• DP 𝑘 : {0, 1} 𝑛 × {0, 1} 𝑑 → {0, 1} 𝑑+𝑘 is called a pseudorandom generator function and
computable in time poly(𝑛/𝜖). (Intuitively, DP 𝑘 takes the 𝑛-bit truth table of a candidate “hard”
function as well as a 𝑑-bit seed and outputs a pseudorandom sequence of length 𝑑 + 𝑘.)
• 𝐴𝐷 : {0, 1} 𝑛 × {0, 1} 𝑟 → {0, 1} 𝑎 is called an advice function and computable in time poly(𝑛/𝜖)
given oracle access to 𝐷 : {0, 1} 𝑑+𝑘 → {0, 1}.
• 𝑅 𝐷 : {0, 1} 𝑎 × {0, 1} 𝑟 → {0, 1} 𝑛 is called a reconstruction procedure and computable in time
poly(𝑛/𝜖) given oracle access to 𝐷 : {0, 1} 𝑑+𝑘 → {0, 1}.
• The seed length 𝑑 is at most poly(𝑛/𝜖), the advice complexity 𝑎 is at most 𝑘 + 𝑂(log(𝑘/𝜖)), and
the randomness complexity 𝑟 is at most poly(𝑛/𝜖).
• For any string 𝑥 and any function 𝐷 that 𝜖-distinguishes the output distribution of DP 𝑘 (𝑥, -) from
the uniform distribution, it holds that
Pr [𝑅 𝐷 (𝐴𝐷 (𝑥, 𝑤), 𝑤) = 𝑥] ≥ 3/4.
𝑤∼{0,1} 𝑟
For completeness, we present a proof of Theorem 3.1. We make use of the following
list-decodable error-correcting code, which can be constructed by concatenating a Reed-Solomon
code with an Hadamard code.
Lemma 3.2 ([67]; see, e. g., [74]). For any parameters 𝑛 ∈ ℕ and 𝜖 > 0, there exists a function
Enc𝑛,𝜖 : {0, 1} 𝑛 → {0, 1}b𝑛 such that
𝑛 = 2ℓ for some integer ℓ ∈ ℕ and b
• b 𝑛 ≤ poly(𝑛/𝜖),
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 22
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
• Enc𝑛,𝜖 is computable in time poly(𝑛/𝜖), and
• given 𝑦 ∈ {0, 1}b𝑛 , one can find a list of size poly(1/𝜖) that contains all the strings 𝑥 ∈ {0, 1} 𝑛
such that 𝑦 and Enc𝑛,𝜖 (𝑥) agree on at least a (1/2 + 𝜖)-fraction of coordinates.
Proof of Theorem 3.1. We describe the pseudorandom generator function
DP 𝑘 : {0, 1} 𝑛 × {0, 1} 𝑑 → {0, 1} 𝑑+𝑘 ,
which we call a 𝑘-wise direct product generator. Let Enc𝑛,𝛿 denote the error-correcting code of
Lemma 3.2, where 𝛿 := 𝜖/2𝑘, and let b 𝑥 : {0, 1}ℓ → {0, 1} be the function specified by the truth
ℓ
table Enc𝑛,𝛿 (𝑥) ∈ {0, 1} , where ℓ = 𝑂(log(𝑛/𝜖)). The 𝑘-wise direct product generator is defined
2
as
DP 𝑘 (𝑥, 𝑧¯ ) := (𝑧 1 , · · · , 𝑧 𝑘 , b 𝑥 (𝑧 𝑘 ))
𝑥 (𝑧 1 ), · · · , b
𝑘
for any 𝑧¯ = (𝑧 1 , · · · , 𝑧 𝑘 ) ∈ {0, 1}ℓ . The seed length of DP 𝑘 is 𝑑 := ℓ 𝑘 = 𝑂(𝑘 log(𝑛/𝜖)).
We first present a reconstruction procedure 𝑅0 with small success probability; then we will
amplify the success probability to 3/4.10
Claim 3.3. There exist an advice function 𝐴0 : {0, 1} 𝑛 × {0, 1} 𝑟0 → {0, 1} 𝑘 and a reconstruction
procedure 𝑅 0𝐷 : {0, 1} 𝑎0 × {0, 1} 𝑟0 → {0, 1} 𝑛 such that
𝜖 1
Pr[𝑅 0𝐷 (𝐴0 (𝑥, 𝑤), 𝑤) = 𝑥] ≥ · ,
𝑤 2𝑘 𝐿
where 𝑟0 = 𝑂(𝑑) and 𝐿 = poly(𝑘/𝜖) denotes the list size of Lemma 3.2.
Proof. Claim 3.3 can be proved by using a standard hybrid argument (as in [56, 74]). Assume
that 𝐷 : {0, 1} 𝑑+𝑘 → {0, 1} satisfies
Pr 𝐷(𝑧 1 , · · · , 𝑧 𝑘 , b 𝑥 (𝑧 𝑘 )) = 1 − Pr 𝐷(𝑧 1 , · · · , 𝑧 𝑘 , 𝑏1 , · · · , 𝑏 𝑘 ) = 1 ≥ 𝜖.
𝑥 (𝑧 1 ), · · · , b
𝑧¯ 𝑧¯ ,𝑏
For any 𝑖 ∈ {0, · · · , 𝑘}, define the 𝑖th hybrid distribution 𝐻𝑖 as the distribution of
(𝑧 1 , · · · , 𝑧 𝑘 , b 𝑥 (𝑧 𝑖 ), 𝑏 𝑖+1 , · · · , 𝑏 𝑘 ),
𝑥 (𝑧 1 ), · · · , b
𝑘
where 𝑧¯ = (𝑧 1 , · · · , 𝑧 𝑘 ) ∼ {0, 1}ℓ and 𝑏 𝑖+1 , · · · , 𝑏 𝑘 ∼ {0, 1}. By this definition, 𝐻0 is identically
distributed with the uniform distribution, and 𝐻 𝑘 is an identical distribution with DP 𝑘 (𝑥, 𝑧¯ ).
Therefore,
𝜖
𝔼 [𝐷(𝐻𝑖 ) − 𝐷(𝐻𝑖−1 )] ≥ .
𝑖∼[𝑘] 𝑘
𝑧¯ ,𝑏
10We amplify the success probability so that the proof of Theorem 1.4 is clearer, although a proof can be given
without the amplification.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 23
S HUICHI H IRAHARA
By an averaging argument, we obtain
𝜖 𝜖
Pr 𝔼 [𝐷(𝐻𝑖 ) − 𝐷(𝐻𝑖−1 )] ≥ ≥ . (3.1)
𝑖∼[𝑘],𝑏 𝑧 𝑖 ∼{0,1}ℓ 2𝑘 2𝑘
𝑧 1 ,··· ,𝑧 𝑖−1 ,𝑧 𝑖+1 ,··· ,𝑧 𝑘
Define the advice function 𝐴0 as 𝐴0 (𝑥, 𝑤) := (b 𝑥 (𝑧 𝑖−1 ), 𝑏 𝑖 , · · · , 𝑏 𝑘 ) ∈ {0, 1} 𝑘 , where 𝑤
𝑥 (𝑧 1 ), · · · , b
is a coin flip sequence that contains the random choice of 𝑖 ∼ [𝑘], 𝑧 1 , · · · , 𝑧 𝑖−1 ∼ {0, 1}ℓ , and
𝑏 ∼ {0, 1} 𝑘 . By a standard calculation (see, e. g., [74, Proposition 7.16]), it follows from Eq. (3.1)
that
1 𝜖
𝐷(¯𝑧 , 𝐴0 (𝑥, 𝑤)) ⊕ 1 ⊕ 𝑏 𝑖 = b 𝑥 (𝑧 𝑖 ) ≥ +
Pr (3.2)
𝑖
𝑧 ∼{0,1} ℓ 2 2𝑘
with probability at least 𝜖/2𝑘 over the random choice of (𝑖, 𝑧 [𝑘]\{𝑖} , 𝑏).
Now we describe the reconstruction procedure 𝑅 0𝐷 (𝛼, 𝑤). Given an advice string 𝛼 ∈ {0, 1} 𝑘
and a coin flip 𝑤, we regard the random bits 𝑤 as 𝑖 ∼ [𝑘], 𝑧 1 , · · · , 𝑧 𝑖−1 , 𝑧 𝑖+1 , · · · , 𝑧 𝑘 ∼ {0, 1}ℓ ,
ℓ
𝑏 ∼ {0, 1} 𝑘 , and 𝑗 ∼ [𝐿]. Define a string 𝑦 ∈ {0, 1}2 as
𝑦 𝑧 𝑖 := 𝐷(¯𝑧 , 𝛼) ⊕ 1 ⊕ 𝑏 𝑖
for every 𝑧 𝑖 ∈ {0, 1}ℓ . The reconstruction procedure uses the list-decoding algorithm of
Lemma 3.2 to obtain a list of all the 2ℓ -bit strings that agree with 𝑦 on a (1/2 + 𝜖/2𝑘)-fraction of
indices, and outputs the 𝑗th string in the list.
We claim that Pr𝑤 [𝑅 0𝐷 (𝐴0 (𝑥, 𝑤), 𝑤) = 𝑥] ≥ 𝜖/2𝑘𝐿. By Eq. (3.2), with probability at least 𝜖/2𝑘
over the random choice of (𝑖, 𝑧 [𝑘]\{𝑖} , 𝑏), the list-decoding algorithm outputs a list of size 𝐿 that
contains 𝑥. With probability at least 1/𝐿 over the choice of 𝑗 ∼ [𝐿], it holds that 𝑥 is the 𝑗th string
in the list, in which case 𝑅0𝐷 (𝐴0 (𝑥, 𝑤), 𝑤) = 𝑥. Therefore, we obtain
𝜖 1
Pr[𝑅0𝐷 (𝐴0 (𝑥, 𝑤), 𝑤) = 𝑥] ≥ · .
𝑤 2𝑘 𝐿
It remains to amplify the success probability. Intuitively, we repeat picking coin flip sequences
𝑡 = 𝑂(𝑘𝐿/𝜖) times, and provide the successful index 𝑖 ∈ [𝑡] as an advice string. Details follow.
The advice function 𝐴𝐷 : {0, 1} 𝑛 × ({0, 1} 𝑟0 )𝑡 → {0, 1} 𝑘+𝑂(log 𝑡) takes an 𝑛-bit string 𝑥 and coin
flip sequences (𝑤 1 , · · · , 𝑤 𝑡 ) ∈ ({0, 1} 𝑟0 )𝑡 and outputs (𝐴 𝑖 (𝑥, 𝑤 𝑖 ), 𝑖) ∈ {0, 1} 𝑘 × [𝑡], where 𝑖 is the
first index 𝑖 ∈ [𝑡] such that 𝑅 0𝐷 (𝐴0 (𝑥, 𝑤 𝑖 ), 𝑤 𝑖 ) = 𝑥; if there is no such 𝑖, the output of 𝐴𝐷 is arbitrary.
Given an advice string (𝛼, 𝑖) ∈ {0, 1} 𝑘 × [𝑡] and coin flip sequences 𝑤¯ = (𝑤1 , · · · , 𝑤 𝑡 ) ∈ ({0, 1} 𝑟0 )𝑡 ,
we define 𝑅 𝐷 ((𝛼, 𝑖), 𝑤)¯ = 𝑅 0𝐷 (𝛼, 𝑤 𝑖 ). The failure probability is
Pr 𝑅 𝐷 (𝐴𝐷 (𝑥, 𝑤),
¯ 𝑤)¯ ≠ 𝑥 = Pr ∀𝑖 ∈ [𝑡], 𝑅0𝐷 (𝐴0 (𝑥, 𝑤 𝑖 ), 𝑤 𝑖 ) ≠ 𝑥 ≤ (1 − 𝜖/2𝑘𝐿)𝑡 ≤ 1/4,
𝑤¯ 𝑤¯
where the last inequality holds for a sufficiently large 𝑡 = 𝑂(𝑘𝐿/𝜖).
One of important ingredients of the proof of Theorem 1.4 is a pseudorandom generator
constructed by Buhrman, Fortnow, and Pavan [10].
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 24
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
Lemma 3.4 (Buhrman, Fortnow, and Pavan [10]). If DistNP ⊆ AvgP, then there exist a constant 𝑐
and a pseudorandom generator 𝐺 = {𝐺 𝑛 : {0, 1} 𝑐 log 𝑛 → {0, 1} 𝑛 } 𝑛∈ℕ that (1/𝑛)-fools size-𝑛 circuits.
The direct product generator construction (Theorem 3.1) achieves small advice complexity
𝑎; however, a disadvantage is that the randomness complexity 𝑟 is large. The pseudorandom
generator of Lemma 3.4 enables us to reduce the randomness complexity effectively.
Another ingredient is the fact that DistNP𝐴 ⊆ AvgP implies that a dense subset of 𝐴-oracle
time-bounded Kolmogorov-random strings can be rejected in polynomial time.
Lemma 3.5 ([32]). Assume that DistNP𝐴 ⊆ AvgP. Then, there exists a polynomial-time algorithm 𝑀
such that
1. 𝑀(𝑥, 1𝑡 ) = 1 for every 𝑥 such that K𝑡,𝐴 (𝑥) < |𝑥| − 1, and
2. Pr𝑥∼{0,1}𝑛 𝑀(𝑥, 1𝑡 ) = 0 ≥ 14 for every 𝑛 ∈ ℕ and every 𝑡 ∈ ℕ .
Proof Sketch. We consider a distributional problem (𝐿, 𝒟) defined as follows. The language
𝐿 ∈ NP𝐴 is the problem of deciding whether K𝑡,𝐴 (𝑥) < |𝑥| − 1 on input (𝑥, 1𝑡 ). A distribution
𝒟𝑚 picks 𝑡 ∼ [𝑚] and 𝑥 ∼ {0, 1} 𝑚−𝑡 and outputs (𝑥, 1𝑡 ). Since the fraction of Yes instances in
𝐿 is at most 12 for any fixed 𝑡, any errorless heuristic algorithm that solves (𝐿, 𝒟) must reject a
1
4 -fraction of inputs. Details can be found in [32].
Now we are ready to prove Theorem 1.4.
Proof of Theorem 1.4. Under the assumption that DistNP𝐴 ⊆ AvgP, we have the secure pseu-
dorandom generator 𝐺 = {𝐺 𝑚 : {0, 1} 𝑐0 log 𝑚 → {0, 1} 𝑚 } 𝑚∈ℕ of Lemma 3.4. In particular,
by replacing random bits used by randomized algorithms with the output of 𝐺, we obtain
Promise-BPP = Promise-P; thus it suffices to present a randomized polynomial-time algorithm
𝑀1 for computing Gap𝜏 (K𝐴 vs K) for some polynomial 𝜏.
Fix any input (𝑥, 1𝑠 , 1𝑡 ), where 𝑥 ∈ {0, 1}∗ is a string of length 𝑛 ∈ ℕ and 𝑠, 𝑡 ∈ ℕ . Take the
𝑘-wise direct product generator DP 𝑘 (𝑥, -) : {0, 1} 𝑑 → {0, 1} 𝑑+𝑘 of Theorem 3.1, where 𝑘 is some
parameter chosen later and 𝜖 := 18 . Let 𝑀0 be the polynomial-time algorithm 𝑀 of Lemma 3.5.
Let 𝜏0 be some polynomial chosen later.
The randomized algorithm 𝑀1 operates as follows. On input (𝑥, 1𝑠 , 1𝑡 ), 𝑀1 samples a
string 𝑧 ∼ {0, 1} 𝑑 uniformly at random. Then, 𝑀1 simulates 𝑀0 on input (DP 𝑘 (𝑥, 𝑧), 1𝑡 ), where
0
𝑡 0 := 𝜏0 (𝑛, 𝑡), and accepts if and only if 𝑀0 accepts. (That is, 𝑀1 (𝑥, 1𝑠 , 1𝑡 ) is defined to be
𝑀0 (DP 𝑘 (𝑥, 𝑧), 1𝑡 ) for a random 𝑧 ∼ {0, 1} 𝑑 .)
0
We claim the correctness of the algorithm 𝑀1 below.
Claim 3.6.
1. If K𝑡,𝐴 (𝑥) ≤ 𝑠, then 𝑀1 (𝑥, 1𝑠 , 1𝑡 ) accepts with probability 1.
2. If K𝜏(𝑛,𝑡) (𝑥) > 𝑠 + log 𝜏(𝑛, 𝑡), then 𝑀1 (𝑥, 1𝑠 , 1𝑡 ) rejects with probability at least 81 .
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 25
S HUICHI H IRAHARA
We claim the first item. Fix any 𝑧 ∈ {0, 1} 𝑑 . Since the output DP 𝑘 (𝑥, 𝑧) of the direct product
generator can be described by 𝑛, 𝑘 ∈ ℕ , the seed 𝑧 ∈ {0, 1} 𝑑 and the program for describing 𝑥 of
size K𝑡,𝐴 (𝑥) in time 𝑡 0 = 𝜏0 (𝑛, 𝑡), where 𝜏0 is some polynomial, it holds that
K𝑡 ,𝐴 (DP 𝑘 (𝑥, 𝑧)) ≤ 𝑑 + K𝑡,𝐴 (𝑥) + 𝑐 1 log 𝑛,
0
(3.3)
for some constant 𝑐1 . We set 𝑘 := 𝑠 + 𝑐1 log 𝑛 +2. Note that under the assumption that K𝑡,𝐴 (𝑥) ≤ 𝑠,
Eq. (3.3) is less than 𝑑 + 𝑘 − 1. Therefore, by Lemma 3.5, 𝑀0 (DP 𝑘 (𝑥, 𝑧)) = 1 for every 𝑧 ∈ {0, 1} 𝑑 ;
thus 𝑀1 accepts.
Next, we claim the second item, by proving its contrapositive. Assume that 𝑀1 (𝑥, 1𝑠 , 1𝑡 )
rejects with probability less than 18 . This means that
1
𝑀0 (DP 𝑘 (𝑥, 𝑧), 1𝑡 ) = 0 < .
Pr
𝑧∼{0,1} 𝑑 8
On the other hand, by Lemma 3.5, we also have
1
𝑀0 (𝑤, 1𝑡 ) = 0 ≥ .
Pr
𝑤∼{0,1} 𝑑+𝑘 4
Therefore,
1
𝑀0 (𝑤, 1𝑡 ) = 0 − 𝑀0 (DP 𝑘 (𝑥, 𝑧), 1𝑡 ) = 0 ≥ ,
Pr Pr
𝑤∼{0,1} 𝑑+𝑘 𝑧∼{0,1} 𝑑 8
which means that a function 𝐷 defined as 𝐷(𝑤) := ¬𝑀0 (𝑤, 1𝑡 ) distinguishes DP 𝑘 (𝑥, -) from the
uniform distribution. By the reconstruction property of Theorem 3.1,
3
𝑅 𝐷 (𝐴𝐷 (𝑥, 𝜌), 𝜌) = 𝑥 ≥ ,
Pr (3.4)
𝜌∼{0,1} 𝑟 4
where the advice complexity 𝑎 is at most 𝑘 + 𝑂(log(𝑘/𝜖)) = 𝑠 + 𝑂(log(𝑛/𝜖)).11 Now we
derandomize the random choice of 𝜌 of Eq. (3.4) by using the secure pseudorandom generator
𝐺 = {𝐺 𝑚 } 𝑚∈ℕ . That is, we argue that 𝜌 can be replaced with 𝐺 𝑚 (𝜌0 ) for some short seed
𝜌0 , which enables us to obtain a short description for 𝑥. To this end, consider a statistical
test 𝑇 : {0, 1} 𝑟 → {0, 1} that checks the condition of Eq. (3.4); that is, 𝑇(𝜌) = 1 if and only if
𝑅 𝐷 (𝐴𝐷 (𝑥, 𝜌), 𝜌) = 𝑥. One can easily observe that 𝑇 can be implemented by a circuit of size
𝑚 := poly(𝑛, 𝑡).
Now we replace the random bits 𝜌 ∈ {0, 1} 𝑟 with the first 𝑟 bits of the pseudorandom
sequence 𝐺 𝑚 (𝜌0 ). By Eq. (3.4), we have
Pr [𝑇(𝐺(𝜌0 )) = 1] ≥ Pr [𝑇(𝜌) = 1] − 𝑜(1) > 0.
𝜌0 ∼{0,1} 𝑐0 log 𝑚 𝜌∼{0,1} 𝑟
In particular, there exists a seed 𝜌0 ∈ {0, 1} 𝑐0 log 𝑚 such that 𝑇(𝐺 𝑚 (𝜌0 )) = 1.
11We may assume without loss of generality that 𝑘 := 𝑠 + 𝑂(log 𝑛) ≤ 2𝑛, as otherwise K𝑡,𝐴 (𝑥) ≤ 𝑠 always holds.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 26
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
We are ready to present the algorithm for describing 𝑥. In order to describe 𝑥, it takes as
a description 𝑛, 𝑡, 𝑚 ∈ ℕ , the seed 𝜌0 ∈ {0, 1} 𝑐0 log 𝑚 , and the advice string 𝛼 := 𝐴𝐷 (𝐺 𝑚 (𝜌0 )) ∈
{0, 1} 𝑎 . Since 𝑇(𝐺 𝑚 (𝜌0 )) = 1, the string 𝑥 is equal to 𝑅 𝐷 (𝛼, 𝐺 𝑚 (𝜌0 )), which can be computed in
time 𝜏1 (𝑛, 𝑡) for some polynomial 𝜏1 . Therefore,
K𝜏1 (𝑛,𝑡) (𝑥) ≤ 𝑎 + 𝑐0 log 𝑚 + 𝑂(log 𝑛𝑡) ≤ 𝑠 + 𝑂(log 𝑛𝑡).
In particular, by choosing a polynomial 𝜏 large enough, we have
K𝜏(𝑛,𝑡) (𝑥) ≤ K𝜏1 (𝑛,𝑡) (𝑥) ≤ 𝑠 + log 𝜏(𝑛, 𝑡).
This completes the proof of Claim 3.6.
Since 𝑀1 is a one-sided-error algorithm, the success probability can be amplified by repeating
the computation of 𝑀1 for independent random coin flips. We thus conclude that Gap𝜏 (K𝐴 vs K)
is in Promise-BPP = Promise-P.
An important corollary is that NP-hardness of Gap(K𝐴 vs K) for some 𝐴 ∈ PH is sufficient
for proving an equivalence between worst-case and average-case complexity of PH.
Restatement of Corollary 1.6. Assume that Gap(K𝐴 vs K) is “NP-hard” for some 𝐴 ∈ PH in the
sense that
NP ⊄ BPP =⇒ Gap(K𝐴 vs K) ∉ P.
Then,
DistPH ⊄ AvgP ⇐⇒ PH ≠ P.
Proof. It is obvious that PH = P implies that DistPH ⊆ AvgP. We prove the converse direction.
Assume that DistPH ⊆ AvgP. By Theorem 1.4, we obtain Gap(K𝐴 vs K) ∈ P for any 𝐴 ∈ PH. It
follows from the contrapositive of the assumption that NP ⊆ BPP; moreover, by Lemma 3.4, we
also have BPP = P. Therefore, we obtain NP = P, which is equivalent to PH = P.
Another corollary is a relationship between time-bounded Kolmogorov complexity and its
PH-oracle version, which can be proved by using the disjointness of Gap(K𝐴 vs K).
Corollary 3.7. If DistPH ⊆ AvgP, then, for any 𝐴 ∈ PH, there exists a polynomial 𝜏 such that
K𝜏(|𝑥|,𝑡) (𝑥) ≤ K𝑡,𝐴 (𝑥) + log 𝜏(|𝑥|, 𝑡)
for any 𝑥 ∈ {0, 1}∗ and 𝑡 ∈ ℕ .
Proof. By Theorem 1.4, under the assumption that DistNP𝐴 ⊆ DistPH ⊆ AvgP, there exists an
algorithm 𝑀 such that 𝑀(𝑥, 1𝑠 , 1𝑡 ) = 1 for every 𝑥 such that K𝑡,𝐴 (𝑥) ≤ 𝑠 and 𝑀(𝑥, 1𝑠 , 1𝑡 ) = 0 for
every 𝑥 such that K𝜏(|𝑥|,𝑡) (𝑥) > 𝑠 + log 𝜏(|𝑥|, 𝑡), for any 𝑠 ∈ ℕ and 𝑡 ∈ ℕ . For any 𝑥 ∈ {0, 1}∗ and
𝑡 ∈ ℕ , define 𝑠 := K𝑡,𝐴 (𝑥); since 0 ≠ 𝑀(𝑥, 1𝑠 , 1𝑡 ) = 1, we obtain K𝜏(|𝑥|,𝑡) (𝑥) ≤ 𝑠 + log 𝜏(|𝑥|, 𝑡).
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 27
S HUICHI H IRAHARA
Under the plausible assumption that ENP ≠ E, we observe that Gap(KSAT vs K) is non-disjoint.
Proposition 3.8. If ENP ≠ E, then, for some polynomial 𝜏0 and any polynomial 𝜏, there are infinitely
many strings 𝑥 such that K𝑡,SAT (𝑥) = 𝑂(log |𝑥|) and K𝜏(|𝑥|) (𝑥) > log 𝜏(|𝑥|), where 𝑡 := 𝜏0 (|𝑥|).
Proof. By [12], the assumption is equivalent to ENP ⊄ E/𝑂(𝑛). Take a language 𝐿 ∈ ENP \ E/𝑂(𝑛).
For each 𝑛 ∈ ℕ , define 𝑥 𝑛 to be the truth table of length 2𝑛 that encodes the characteristic function
of 𝐿 ∩ {0, 1} 𝑛 . Since 𝑥 𝑛 can be described in time 𝜏0 (|𝑥 𝑛 |) = poly(|𝑥 𝑛 |) given 𝑛 ∈ ℕ and oracle
access to SAT, we have K𝑡,SAT (𝑥 𝑛 ) = 𝑂(log |𝑥 𝑛 |). On the other hand, if K𝜏(|𝑥 𝑛 |) (𝑥 𝑛 ) ≤ log 𝜏(|𝑥 𝑛 |)
for all large 𝑛 ∈ ℕ , there exists an advice string of length log 𝜏(|𝑥 𝑛 |) = 𝑂(𝑛) that makes it possible
to compute 𝐿 ∩ {0, 1} 𝑛 in time poly(𝜏(|𝑥 𝑛 |)) = 2𝑂(𝑛) , which contradicts 𝐿 ∉ E/𝑂(𝑛).
Finally, we observe that the complexity of Gap(KSAT vs K) is closely related to the complexity
of MINKT.
Proposition 3.9. For any polynomial 𝜏, the following hold.
• Gap𝜏 (K vs K) is reducible to Gap𝜏 (KSAT vs K) via an identity map.
• If Gap𝜏 (KSAT vs K) is disjoint, then Gap𝜏 (KSAT vs K) is reducible to MINKT; in particular,
Gap𝜏 (KSAT vs K) ∈ NP.
Proof. The first item is obvious because K𝑡,SAT (𝑥) ≤ K𝑡 (𝑥) for any 𝑡 ∈ ℕ and 𝑥 ∈ {0, 1}∗ . For the
second item, let (ΠYes , ΠNo ) denote Gap𝜏 (KSAT vs K). Since (ΠNo , ΠNo ) is a problem of checking
whether K𝜏(|𝑥|,𝑡) (𝑥) ≤ 𝑠 + log 𝜏(|𝑥|, 𝑡) given (𝑥, 1𝑠 , 1𝑡 ) as input, it is reducible to MINKT. In
particular, (ΠYes , ΠNo ) ∈ NP holds under the assumption that it is disjoint.
3.2 Gap(𝐹 vs 𝐹 −1 ): PRG construction from one-way functions
Håstad, Impagliazzo, Levin, and Luby [30] showed that a cryptographic pseudorandom generator
can be constructed from any one-way function. In this section, we view the black-box PRG
construction from a meta-computational perspective, which leads us to the promise problem
Gap(𝐹 vs 𝐹 −1 ), which is a problem of asking whether a given function 𝑓 is computable by a
small circuit or 𝑓 is hard to invert by any small circuit. Here we assume that the function
𝑓 : {0, 1} 𝑛 → {0, 1} 𝑛 is given as oracle, and we focus on an algorithm that runs in time poly(𝑛).
In other words, we consider a sublinear-time algorithm that is given random access to the truth
table of 𝑓 .
Definition 3.10. For a function 𝜏 : ℕ × ℕ → ℕ , Gap𝜏 (𝐹 vs 𝐹 −1 ) is a promise problem (ΠYes , ΠNo )
defined as follows. The input consists of a size parameter 𝑠 ∈ ℕ , an integer 𝑛 ∈ ℕ , and black-box
access to a function 𝑓 : {0, 1} 𝑛 → {0, 1} 𝑛 .
• The set ΠYes consists of inputs (𝑛, 𝑠, 𝑓 ) such that size( 𝑓 ) ≤ 𝑠.
• The set ΠNo consists of inputs (𝑛, 𝑠, 𝑓 ) such that, for any oracle circuit 𝐶 of size 𝜏(𝑛, 𝑠),
1
𝐶 𝑓 ( 𝑓 (𝑥)) ∈ 𝑓 −1 ( 𝑓 (𝑥)) < .
Pr
𝑥∼{0,1} 𝑛 2
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 28
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
Theorem 3.11. If DistNP ⊆ AvgP, then there exist a polynomial 𝜏 and a coRP-type randomized
algorithm 𝑀 that solves Gap𝜏 (𝐹 vs 𝐹 −1 ) = (ΠYes , ΠNo ) on input (𝑛, 𝑠) in time poly(𝑛, 𝑠). That is, 𝑀
is a randomized oracle algorithm such that
1. Pr𝑀 [𝑀 𝑓 (𝑛, 𝑠) = 1] = 1 for every (𝑛, 𝑠, 𝑓 ) ∈ ΠYes ,
2. Pr𝑀 [𝑀 𝑓 (𝑛, 𝑠) = 0] ≥ 12 for every (𝑛, 𝑠, 𝑓 ) ∈ ΠNo , and
3. 𝑀 𝑓 (𝑛, 𝑠) runs in time poly(𝑛, 𝑠).
For the proof, we make use of the following black-box construction of a pseudorandom
generator based on any one-way function.
Lemma 3.12 (A black-box PRG Construction from Any OWF [30]). There exists a polynomial 𝑑 =
(-)
𝑑(𝑛) such that, for a parameter 𝑚 ∈ ℕ , there exists a polynomial-time oracle algorithm 𝐺 𝑚 : {0, 1} 𝑑(𝑛) →
𝑚 𝑛 𝑛
{0, 1} that takes a function 𝑓 : {0, 1} → {0, 1} and there exists an oracle algorithm 𝑅 such that, for
any function 𝐷 : {0, 1} 𝑚 → {0, 1}, if 𝑚 > 𝑑 and
1
𝐷(𝐺 𝑓 (𝑧)) = 1 − ,
Pr Pr [𝐷(𝑤) = 1] ≥
𝑧∼{0,1} 𝑛 𝑤∼{0,1} 𝑚 8
then
1
Pr [𝑅 𝑓 ,𝐷 ( 𝑓 (𝑥)) ∈ 𝑓 −1 ( 𝑓 (𝑥))] ≥ .
𝑥,𝑅 2
(-)
The running time of 𝐺 𝑚 and 𝑅 is at most poly(𝑛, 𝑚).
Proof Sketch. Since a weakly one-way function exists if and only if a strongly one-way function
exists ([77]), it suffices to present a reduction that inverts 𝑓 with probability at least 1/poly(𝑛, 𝑚).
(To be more specific, we first amplify the hardness of 𝑓 by taking a direct product 𝑓 𝑡 (𝑥 1 , · · · , 𝑥 𝑡 ) :=
( 𝑓 (𝑥 1 ), · · · , 𝑓 (𝑥 𝑡 )), where 𝑡 is some appropriately chosen parameter, and then apply the HILL
construction to 𝑓 𝑡 described below.)
𝑓
We invoke the pseudorandom generator construction 𝐺HILL of Håstad, Impagliazzo, Levin,
and Luby [30] based on 𝑓 . They presented a security reduction 𝑅 such that if there exists a
𝑓
function 𝐷 that distinguishes 𝐺HILL from the uniform distribution, then an oracle algorithm
𝑅 𝑓 ,𝐷 ( 𝑓 (𝑥)) can compute an element in 𝑓 −1 ( 𝑓 (𝑥)) with probability at least 1/poly(𝑛, 𝑚) over the
choice of 𝑥 ∼ {0, 1} 𝑛 and the internal randomness of 𝑅.
Proof of Theorem 3.11. Let 𝐺 (-) be the black-box pseudorandom generator construction of
Lemma 3.12, and let 𝑅 be the security reduction of Lemma 3.12.
Under the assumption that DistNP ⊆ AvgP, by Lemma 3.5, there exists a polynomial-time
algorithm 𝑀 such that 𝑀(𝑥, 1𝑡 ) = 1 for every 𝑥 such that K𝑡 (𝑥) < |𝑥| − 1, and
1
𝑀(𝑥, 1𝑡 ) = 0 ≥
Pr
𝑥∼{0,1} 𝑛 4
for every 𝑛 ∈ ℕ and every 𝑡 ∈ ℕ .
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 29
S HUICHI H IRAHARA
The algorithm 𝑀 0 for computing Gap(𝐹 vs 𝐹 −1 ) is defined as follows. Let 𝑓 : {0, 1} 𝑛 → {0, 1} 𝑛
and 𝑠 ∈ ℕ be inputs. Define 𝑚 := 𝑝(𝑛, 𝑠) for some polynomial 𝑝 chosen later. Pick a random
𝑓
𝑧 ∈ {0, 1} 𝑛 . Then 𝑀 0 accepts if and only if 𝑀(𝐺 𝑚 (𝑧), 1𝑡 ) accepts for a sufficiently large
𝑡 = poly(𝑛, 𝑠).
We claim the correctness of 𝑀 0 below.
Claim 3.13.
1. 𝑀 0 accepts any 𝑓 such that size( 𝑓 ) ≤ 𝑠 with probability 1.
2. 𝑀 0 rejects any 𝑓 such that Pr𝑥 𝐶 𝑓 ( 𝑓 (𝑥)) ∈ 𝑓 −1 ( 𝑓 (𝑥)) < 12 with probability at least 18 .
We claim that any 𝑓 such that size( 𝑓 ) ≤ 𝑠 is accepted by the algorithm 𝑀 0. Indeed, since 𝑓 is
𝑓
computable by some circuit of size 𝑠 and 𝐺 𝑚 is polynomial-time-computable, the output of the
𝑓
generator 𝐺 𝑚 (𝑧) can be described by using the description of the circuit of size 𝑠, the seed 𝑧 of
length 𝑑(𝑛), and 𝑛, 𝑚 ∈ ℕ in polynomial time; thus, for a sufficiently large 𝑡 = poly(𝑛, 𝑠),
𝑓
K𝑡 (𝐺 𝑚 (𝑧)) ≤ 𝑑(𝑛) + 𝑂(𝑠)
e + 𝑂(log 𝑛).
Choosing 𝑚 = 𝑝(𝑛, 𝑠) large enough, this is bounded by 𝑚 − 2. Thus 𝑀 0 accepts.
Conversely, suppose that the algorithm 𝑀 0 accepts with probability at least 78 . This means
that i 7
𝑓
h
Pr 𝑀(𝐺 𝑚 (𝑧), 1𝑡 ) = 1 ≥ .
𝑧∼{0,1} 𝑛 8
On the other hand, by Lemma 3.5, we have
3
𝑀(𝑤, 1𝑡 ) = 1 ≤ .
Pr
𝑤∼{0,1} 𝑚 4
𝑓
Therefore, 𝑀(-, 1𝑡 ) is a distinguisher for 𝐺 𝑚 . It follows from the property of the security
reduction 𝑅 that h i 1
𝑡
Pr 𝑅 𝑓 ,𝑀(-,1 ) ( 𝑓 (𝑥)) ∈ 𝑓 −1 ( 𝑓 (𝑥)) ≥ .
𝑥,𝑅 2
𝑡
By fixing the internal randomness of 𝑅 and simulating the polynomial-time algorithm 𝑅 𝑓 ,𝑀(-,1 )
by a polynomial-size circuit 𝐶 𝑓 , we conclude that 𝑓 can be inverted by the oracle circuit 𝐶 𝑓 of
size poly(𝑛, 𝑠) =: 𝜏(𝑛, 𝑠). Thus 𝑓 is not a No instance of Gap𝜏 (𝐹 vs 𝐹 −1 ).
Remark 3.14. In fact, the assumption that DistNP ⊆ AvgP of Theorem 3.11 can be weakened to the
assumption that there exists a P-natural property useful against SIZE(2𝑜(𝑛) ) (which is essentially
equivalent to an errorless heuristic algorithm for MCSP [37, 32]). Indeed, as in [2, 63, 4],
the pseudorandom function generator construction of [26] can be used to construct a black-
box pseudorandom generator 𝐺 𝑓 based on a one-way function 𝑓 that satisfies size(𝐺 𝑓 (𝑧)) ≤
poly(|𝑧|, log |𝐺 𝑓 (𝑧)|) for any seed 𝑧 ∈ {0, 1} 𝑑 ; such a pseudorandom generator 𝐺 𝑓 can be
distinguished from the uniform distribution by using the natural property.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 30
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
We now explain that Gap(𝐹 vs 𝐹 −1 ) is conjectured to be non-disjoint. An auxiliary-input one-
way function (AIOWF) 𝑓 = { 𝑓𝑥 : {0, 1} 𝑝(|𝑥|) → {0, 1} 𝑞(|𝑥|) } 𝑥∈{0,1}∗ is a polynomial-time-computable
function such that, for−1some infinite set 𝐼, for any non-uniform polynomial-time algorithm
𝐴, Pr 𝑦 𝐴(𝑥, 𝑓𝑥 (𝑦)) ∈ 𝑓𝑥 ( 𝑓𝑥 (𝑦)) < 1/𝑛 𝜔(1) for all large 𝑛 ∈ ℕ and any 𝑥 ∈ 𝐼. This is a weaker
cryptographic primitive than a one-way function (i. e., the existence of a one-way function implies
that of an auxiliary-input one-way function). Ostrovsky [59] showed that non-triviality of SZK
implies the existence of an auxiliary-input one-way function. (see also [73]). We observe that the
existence of an auxiliary-input one-way function implies the non-disjointness of Gap(𝐹 vs 𝐹 −1 ).
Proposition 3.15. If there exists an auxiliary-input one-way function 𝑓 = { 𝑓𝑥 : {0, 1} 𝑝(|𝑥|) →
{0, 1} 𝑞(|𝑥|) } 𝑥∈{0,1}∗ , then, for any polynomial 𝜏, Gap𝜏 (𝐹 vs 𝐹 −1 ) is non-disjoint.
Proof. Take an infinite set 𝐼 ⊆ {0, 1}∗ that is hard for polynomial-size circuits to invert { 𝑓𝑥 } 𝑥∈𝐼 .
Since 𝑓 is polynomial-time-computable, size( 𝑓𝑥 ) ≤ 𝑛 𝑐 for some constant 𝑐, where 𝑛 = |𝑥|. We
set the size parameter 𝑠 := 𝑛 𝑐 . On the other hand, by the property of AIOWF, for any circuit 𝐴
of size 𝜏(𝑛, 𝑠), it holds that
1
Pr 𝐴(𝑥, 𝑓𝑥 (𝑦)) ∈ 𝑓𝑥−1 ( 𝑓𝑥 (𝑦)) < ,
𝑦 2
for a sufficiently large 𝑥 ∈ 𝐼. This means that 𝑓𝑥 is a Yes and No instance of Gap𝜏 (𝐹 vs 𝐹 −1 ).
An immediate corollary of Theorem 3.11 and Proposition 3.15 is that the existence of AIOWF
implies DistNP ⊄ AvgP (which is already shown in [32]). An interesting open question is to
prove “NP-hardness” of Gap(𝐹 vs 𝐹 −1 ), which has the following important consequence:
Corollary 3.16. If, for any polynomial 𝜏, it is “NP-hard” to solve Gap𝜏 (𝐹 vs 𝐹 −1 ) in time poly(𝑛, 𝑠),
then the worst-case and average-case complexity of NP is equivalent in the sense that P ≠ NP iff
DistNP ⊄ AvgP.
Proof. The assumption that Gap(𝐹 vs 𝐹 −1 ) is “NP-hard” means that, for any polynomial 𝜏, if
there exists a coRP-type algorithm that solves Gap𝜏 (𝐹 vs 𝐹 −1 ) on input (𝑛, 𝑠) in time poly(𝑛, 𝑠),
then NP ⊆ BPP. If DistNP ⊆ AvgP, then Theorem 3.11 implies that there exists some polynomial
𝜏 such that Gap𝜏 (𝐹 vs 𝐹 −1 ) can be solved by a coRP-type algorithm in time poly(𝑛, 𝑠). By the
assumption, we obtain NP ⊆ BPP = P, where the last equality is from Lemma 3.4.
4 Meta-computational view of complexity-theoretic PRG construc-
tions
This section provides a meta-computational view of complexity-theoretic PRG constructions.
The section is organized as follows. In Section 4.1, we give definitions of resource-bounded
Kolmogorov complexity and universal hitting set generators. In Section 4.2, we interpret the
notion of advice using resource-bounded Kolmogorov complexity. Using the (new) notion of
advice, we provide the definition of MCLPs in Section 4.3. In Section 4.4, we present a generic
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 31
S HUICHI H IRAHARA
connection from black-box PRG constructions to MCLPs. Section 4.6 applies the connection
to the specific PRG construction given by Nisan and Wigderson [56], which is reviewed in
Section 4.5. Section 4.7 provides a meta-computational view of hardness amplification theorems,
which gives rise to reductions among different MCLPs. In Section 4.8, we apply our principle to
space-bounded algorithms.
4.1 Universal hitting set generators and Kolmogorov complexity
We review the notion of Kt-complexity and its space-bounded version, and present definitions of
universal hitting set generators. Recall the definition of Levin’s resource-bounded Kolmogorov
complexity.
Definition 4.1 ([50]). For a string 𝑥 ∈ {0, 1}∗ , Levin’s Kt complexity of 𝑥 is defined as
Kt(𝑥) := min{ |𝑑| + 𝑡 | 𝑈 outputs 𝑥 on input 𝑑 in time 2𝑡 },
where 𝑈 is an efficient universal Turing machine.
It is possible to enumerate all the strings 𝑥 such that Kt(𝑥) ≤ 𝑠 in time 2𝑂(𝑠) . The enumeration
algorithm gives rise to a universal time-bounded hitting set generator.
Definition 4.2 (Universal time-bounded hitting set generator). For a function 𝑠 : ℕ → ℕ , define
a universal time-bounded hitting set generator Ht𝑠 = {Ht𝑛𝑠 : {0, 1} 𝑠(𝑛)+1 → {0, 1} 𝑛 } 𝑛∈ℕ so that
Ht𝑛𝑠 (𝑑01𝑡 ) is equal to the output of 𝑈 on input 𝑑 if 𝑈(𝑑) ∈ {0, 1} 𝑛 and 𝑈(𝑑) halts in 2𝑡 time steps,
where 𝑑 ∈ {0, 1}∗ and 𝑡 ∈ ℕ .
The hitting set generator Ht is universal in the sense that, if there exists a secure hitting set
𝑂(𝑠)
generator 𝐺 𝑛 : {0, 1} 𝑠 → {0, 1} 𝑛 computable in time 2𝑠 , then Ht𝑛 : {0, 1} 𝑂(𝑠) → {0, 1} 𝑛 is also
𝑂(𝑠)
secure. Indeed, the image of 𝐺 𝑛 is a subset of that of Ht𝑛 because of the following property.
Proposition 4.3 (Universality of Ht). For every function 𝑠 : ℕ → ℕ and 𝑛 ∈ ℕ , the image of Ht𝑛𝑠
contains every string 𝑥 ∈ {0, 1} 𝑛 such that Kt(𝑥) ≤ 𝑠(𝑛). Moreover, the image of Ht𝑛𝑠 can be enumerated
e 𝑠(𝑛)+log 𝑛 ).
in time 𝑂(2
Proof. Consider any string 𝑥 of length 𝑛 such that Kt(𝑥) ≤ 𝑠(𝑛). By the definition of Kt-
complexity, there exists a description 𝑑 ∈ {0, 1}∗ such that 𝑈(𝑑) outputs 𝑥 in time 2𝑡 for some
𝑡 ≤ 𝑠(𝑛) and |𝑑| ≤ 𝑠(𝑛) − 𝑡. By the definition of Ht𝑛𝑠 , we have Ht𝑛𝑠 (𝑑01𝑡 ) = 𝑥.
The notion of KS-complexity was introduced in [2] as a space-bounded analogue of Kt-
complexity.
Definition 4.4 ([2]). For a string 𝑥 ∈ {0, 1}∗ , the KS-complexity of 𝑥 is defined as
KS(𝑥) := min{ |𝑑| + 𝑠 | 𝑈 outputs 𝑥 on input 𝑑 in space 𝑠 }.
One can modify the definition of the universal time-bounded hitting set generator to a
space-bounded version.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 32
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
Definition 4.5 (Universal space-bounded hitting set generator). For a function 𝑠 : ℕ → ℕ , define
a universal space-bounded hitting set generator HS𝑠 = {HS𝑛𝑠 : {0, 1} 𝑠(𝑛) → {0, 1} 𝑛 } 𝑛∈ℕ so that
HS𝑛𝑠 (𝑑01𝑡 ) is equal to the output of 𝑈 on input 𝑑 if 𝑈(𝑑) ∈ {0, 1} 𝑛 and 𝑈(𝑑) uses at most 𝑡 space,
where 𝑑 ∈ {0, 1}∗ and 𝑡 ∈ ℕ .
Proposition 4.6 (Universality of HS). For every function 𝑠 : ℕ → ℕ and 𝑛 ∈ ℕ , the image of
HS𝑛𝑠 contains every string 𝑥 ∈ {0, 1} 𝑛 such that KS(𝑥) ≤ 𝑠(𝑛). Moreover, HS𝑛𝑠 can be computed in
𝑂(𝑠(𝑛) + log 𝑛) space.
4.2 Length-wise advice and resource-bounded Kolmogorov complexity
In order to define meta-computational circuit lower-bound problems, we modify the standard
notion of advice. Usually, a complexity class with advice such as E/𝑂(𝑛) is defined as a subset
of functions 𝑓 : {0, 1}∗ → {0, 1} that are defined on all the strings of any length. Here, for any
𝑛 ∈ ℕ , we define “DTIME(2𝑂(𝑛) )/𝑛 𝑂(𝑛)” as a subset of functions 𝑓 : {0, 1} 𝑛 → {0, 1}, where the
superscript 𝑛 in “/𝑛 ” is appended in order to emphasize that it depends on 𝑛.
Definition 4.7 (Length-wise advice). For any integers 𝑡, 𝑎, 𝑛 ∈ ℕ , we denote by DTIME(𝑡)/𝑛 𝑎
the class of functions 𝑓 : {0, 1} 𝑛 → {0, 1} such that there exists a Turing machine 𝑀 whose
description length12 is 𝑎 and that outputs 𝑓 (𝑥) on input 𝑥 ∈ {0, 1} 𝑛 in time 𝑡. Similarly, let
DSPACE(𝑡)/𝑛 𝑎 denote the class of functions 𝑓 : {0, 1} 𝑛 → {0, 1} such that there exists a Turing
machine 𝑀 whose description length is 𝑎 and that outputs 𝑓 (𝑥) on input 𝑥 ∈ {0, 1} 𝑛 in space 𝑡.
This definition is slightly different from the standard notion of complexity classes with
advice, but these are essentially the same. In order to clarify the difference, for functions
𝑡, 𝑎 : ℕ → ℕ , let DTIME(𝑡)/KL 𝑎 denote the complexity class DTIME(𝑡) with 𝑎-bit advice strings
in the standard sense of Karp and Lipton [46].13 That is, a function 𝑓 : {0, 1}∗ → {0, 1} is in
DTIME(𝑡)/KL 𝑎 if and only if there exists a Turing machine 𝑀 such that, for any 𝑛 ∈ ℕ , there
exists an advice string 𝛼 𝑛 ∈ {0, 1} 𝑎(𝑛) such that 𝑀 outputs 𝑓 (𝑥) on input (𝑥, 𝛼 𝑛 ) in time 𝑡(𝑛) for
every 𝑥 ∈ {0, 1} 𝑛 . Then, the length-wise advice “/𝑛 ” and the Karp–Lipton advice “/KL ” are
equivalent in the following sense.
Fact 4.8. For any functions 𝑡, 𝑎 : ℕ → ℕ and any family of functions 𝑓 = { 𝑓𝑛 : {0, 1} 𝑛 → {0, 1}} 𝑛∈ℕ
(which is identified with a function 𝑓 : {0, 1}∗ → {0, 1}), the following are equivalent.
1. There exists a constant 𝑐 such that 𝑓 ∈ DTIME(𝑡 0)/KL 𝑎 0, where 𝑡 0(𝑛) := 𝑡(𝑛)𝑐 + 𝑐 and 𝑎 0(𝑛) :=
𝑐 · 𝑎(𝑛) + 𝑐.
2. There exists a constant 𝑐 such that, for any 𝑛 ∈ ℕ , 𝑓𝑛 ∈ DTIME(𝑡(𝑛)𝑐 + 𝑐)/𝑛 𝑐 · 𝑎(𝑛) + 𝑐.
Proof Sketch. If 𝑓 ∈ DTIME(𝑡 0)/KL 𝑎 0, then there exists a machine 𝑀 that takes an advice string
𝛼 𝑛 on inputs of length 𝑛. For each 𝑛 ∈ ℕ , define 𝑀𝑛 to be the machine that, on input
12The description length |𝑑 𝑀 | of a machine 𝑀 can be formally defined by using a universal Turing machine 𝑈.
Specifically, a description 𝑑 𝑀 ∈ {0, 1}∗ of 𝑀 is a string that satisfies 𝑈(𝑑 𝑀 , 𝑥) = 𝑀(𝑥) for every 𝑥.
13It is also common to use the notation DTIME(𝑡(𝑛))/KL 𝑎(𝑛), where 𝑛 is an indeterminate.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 33
S HUICHI H IRAHARA
𝑥, simulates 𝑀 on input (𝑥, 𝛼 𝑛 ); the description length of 𝑀𝑛 is at most 𝑂(|𝛼 𝑛 |), and thus
𝑓𝑛 ∈ DTIME(𝑡(𝑛)𝑂(1) )/𝑛 𝑂(𝑎(𝑛)). Conversely, if, for any 𝑛 ∈ ℕ , there exists a Turing machine
𝑀𝑛 whose description length is 𝑂(𝑎(𝑛)), then a universal Turing machine 𝑈 witnesses 𝑓 ∈
DTIME(𝑡 0)/KL 𝑎 0.
The advice “/𝑛 ” is equivalent to Kt-complexity up to a constant factor in the following sense.
Fact 4.9. For any function 𝑡 : ℕ → ℕ such that 𝑡(𝑛) ≥ 𝑛 and for any family of functions 𝑓 =
{ 𝑓𝑛 : {0, 1} 𝑛 → {0, 1}} 𝑛∈ℕ , the following are equivalent.
1. 𝑓𝑛 ∈ DTIME(𝑡(𝑛)𝑂(1) )/𝑛 𝑂(log 𝑡(𝑛)) for all large 𝑛 ∈ ℕ .
2. Kt( 𝑓𝑛 ) = 𝑂(log 𝑡(𝑛)) for all large 𝑛 ∈ ℕ .
4.3 Meta-computational circuit lower-bound problems (MCLPs)
We define promise problems of distinguishing the truth table of explicit functions (e. g.,
computable in DTIME(2𝑐𝑛 )/𝑛 𝑐𝑛) from the truth table of hard functions (e. g., that cannot be
computed in SIZE(2𝜖𝑛 )). We call these Meta-computational Circuit Lower-bound Problems
(MCLPs).
Definition 4.10 (Meta-computational Circuit Lower-bound Problems; MCLPs). Let ℰ, 𝒟 be
families of functions. The ℰ vs 𝒟 Problem is defined as the following promise problem
(ΠYes , ΠNo ).
ΠYes := { tt( 𝑓 ) | 𝑓 ∈ ℰ },
ΠNo := { tt( 𝑓 ) | 𝑓 ∉ 𝒟 }.
We will mainly consider a non-uniform computational model for computing the ℰ vs 𝒟 Problem;
for 𝑁 ∈ ℕ , we denote by (ℰ vs 𝒟)𝑁 the problem restricted to the input length of 𝑁.
We denote by (E vs 𝒟) a family of problems {E𝑐 vs 𝒟} 𝑐∈ℕ , where E𝑐 := 𝑛∈ℕ DTIME(2𝑐𝑛 )/𝑛 𝑐𝑛.
Ð
For a circuit class ℭ, we say that (E vs 𝒟) is solved by a ℭ-circuit of size 𝑠(𝑁) and denote by
(E vs 𝒟) ∈ i.o.ℭ(𝑠(𝑁)) if, for every constant 𝑐, there exists a family of ℭ-circuits {𝐶 𝑁 } 𝑁 ∈ℕ of
size 𝑠(𝑁) such
that 𝐶 𝑁 solves the promise problem (E𝑐 vs 𝒟)𝑁 for infinitely many 𝑁. We also
denote by E vs SIZE(2𝑜(𝑛) ) a family of problems {E𝑐 vs SIZE(2𝛼𝑛 )} 𝑐∈ℕ ,𝛼>0 .
Similarly, DSPACE(𝑛) vs SIZE(2𝑜(𝑛) ) denotes { 𝑛 𝑐𝑛 vs SIZE(2𝛼𝑛 )}
𝑐∈ℕ ,𝛼>0 .
Ð
𝑛∈ℕ DSPACE(𝑐𝑛)/
The definition of the E vs SIZE(2𝑜(𝑛) ) Problem given here is slightly different from Defini-
tion 1.10 given earlier. In Definition 1.10, we defined the E vs SIZE(2𝑜(𝑛) ) Problem by using the
notion of Kt-complexity; however,
these definitions are essentially
equivalent in light of Fact 4.9.
We justify the notation of DSPACE(𝑛) vs SIZE(2𝑜(𝑛) ) below. One can observe that the open
question whether DSPACE(𝑛) ⊄ i.o.SIZE(2𝑜(𝑛) ) is closely related to the DSPACE(𝑛) vs SIZE(2𝑜(𝑛) )
Problem.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 34
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
Proposition 4.11. The following are equivalent.
1. DSPACE(𝑛) ⊄ i.o.SIZE(2𝜖𝑛 ) for some constant 𝜖 > 0.
2. No circuit can solve the DSPACE(𝑛) vs SIZE(2𝑜(𝑛) ) Problem for all large 𝑛 ∈ ℕ .
(2𝑜(𝑛) ; 1 − 2−𝑜(𝑛) ) Problem for all large 𝑛 ∈ ℕ .
3. No circuit can solve the DSPACE(𝑛) vs SIZE 2
4. There exist some constants 𝑐 ∈ ℕ , 𝛼 > 0 such that, for all large 𝑛 ∈ ℕ , there exists a function
𝑓 : {0, 1} 𝑛 → {0, 1} such that 𝑓 ∈ DSPACE(𝑐𝑛)/𝑛 𝑐𝑛 and 𝑓 ∉ SIZE (2𝛼𝑛 ; 1 − 2−𝛼𝑛 ).
2
Proof. First, observe that Item 3 is equivalent to Item 4. Indeed, Item 4 implies Item 3 by the
definition. Conversely, if Item 4 does not hold, the DSPACE(𝑛) vs SIZE (2𝑜(𝑛) ; 1 − 2−𝑜(𝑛) ) Problem
2
is disjoint; thus, there exists an exponential size circuit that computes the problem, which means
that 4 does not hold.
Next, we claim that Item 1 implies Item 4. By using a locally-decodable error-correcting
code, it can be shown that Item 1 is equivalent to DSPACE(𝑛) ⊄ i.o.SIZE (2𝛼𝑛 ; 1 − 2−𝛼𝑛 ) for some
2
constant 𝛼 > 0 (see [68, 48]). Take a problem 𝐿 ∈ DSPACE(𝑛) \ i.o.SIZE (2𝛼𝑛 ; 1 − 2−𝛼𝑛 ). For each
2
𝑛 ∈ ℕ , let 𝑓𝑛 : {0, 1} 𝑛 → {0, 1} be the characteristic function of 𝐿 ∩ {0, 1} 𝑛 . Then, there exists
a constant 𝑐 such that, for all large 𝑛 ∈ ℕ , 𝑓𝑛 ∈ DSPACE(𝑐𝑛)/𝑛 𝑐𝑛 and 𝑓𝑛 ∉ SIZE (2𝛼𝑛 ; 1 − 2−𝛼𝑛 ),
2
which completes the proof of Item 4. It is immediate from the definition that Item 4 implies
Item 2.
We claim that Item 2 implies Item 1. Let 𝑓 = { 𝑓𝑛 : {0, 1} 𝑛 → {0, 1}} 𝑛∈ℕ be a family of
functions such that 𝑓𝑛 ∈ DSPACE(𝑐𝑛)/𝑛 𝑐𝑛 and 𝑓𝑛 ∉ SIZE(2𝛼𝑛 ) for all large 𝑛 ∈ ℕ . In particular,
for all large 𝑛 ∈ ℕ , there exists some machine 𝑀𝑛 of description length 𝑐𝑛 that computes
𝑓𝑛 (𝑥) on input 𝑥 ∈ {0, 1} 𝑛 in space 𝑐𝑛. Let 𝐿 ⊆ {0, 1}∗ be a language such that (𝑥, 𝑀) ∈ 𝐿 if
and only if the description length of a Turing machine 𝑀 is 𝑐|𝑥| and 𝑀 accepts 𝑥 in space
𝑐|𝑥|. It is clear that 𝐿 ∈ DSPACE(𝑛). Moreover, for all large 𝑛 ∈ ℕ , the characteristic function
of { 𝑥 ∈ {0, 1} 𝑛 | (𝑥, 𝑀𝑛 ) ∈ 𝐿 } is equal to 𝑓𝑛 ; thus, it requires circuits of size 2𝛼𝑛 . Therefore,
𝐿 ∉ i.o.SIZE(2𝛼𝑛/(𝑐+1) ).
It is also possible to define MCLPs whose non-disjointness characterizes other circuit lower
bounds. For example, the EXP/poly vs SIZE(2𝑜(𝑛) ) Problem defined as
( )
𝑛𝑐
Ø
DTIME(2 )/𝑛 𝑛 𝑐 vs SIZE(2𝛼𝑛 )
𝑛∈ℕ 𝑐∈ℕ ,𝛼>0
is non-disjoint if and only if EXP/poly ⊄ SIZE(2𝑜(𝑛) ).
4.4 MCLPs from PRG and HSG constructions
We formalize the notion of black-box PRG and HSG construction and then we present a general
connection between black-box PRG and HSG constructions and meta-computational circuit
lower bound problems.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 35
S HUICHI H IRAHARA
Definition 4.12 (Black-Box PRG and HSG Construction). Let 𝐺 (-) : {0, 1} 𝑑 → {0, 1} 𝑚 be an oracle
algorithm that expects an oracle of the form 𝑓 : {0, 1}ℓ → {0, 1}. Let ℭ be a circuit class and
ℛ (-) be an oracle circuit class. The algorithm 𝐺 is referred to as a black-box ℭ-pseudorandom
generator (resp. ℭ-hitting set generator) construction with ℛ-reconstruction and error parameter 𝜖 if
the following hold.
ℭ-Construction For any seed 𝑧 ∈ {0, 1} 𝑑 , there exists a ℭ-circuit that takes tt( 𝑓 ) as input and
outputs 𝐺 𝑓 (𝑧).
ℛ-Reconstruction For any function 𝑓 : {0, 1}ℓ → {0, 1} and any function 𝐷 : {0, 1} 𝑚 → {0, 1},
if 𝐷 is an 𝜖-distinguisher for 𝐺 𝑓 (resp. 𝐷 𝜖-avoids 𝐺 𝑓 ), then 𝑓 ∈ ℛ 𝐷 .
We now present a generic connection between MCLPs and HSG constructions.
Theorem 4.13. Let 𝐺 (-) : {0, 1} 𝑠 → {0, 1} 𝑚 be a black-box ℭ-construction with ℛ-reconstruction that
takes a function 𝑓 : {0, 1} 𝑛 → {0, 1}. Define 𝑁 := 2𝑛 . Let 𝐻 : {0, 1} 𝑑 → {0, 1} 𝑚 be a function such
that 𝐺 𝑓 (𝑧) ∈ Im(𝐻) for every 𝑓 ∈ ℰ and every 𝑧 ∈ {0, 1} 𝑑 . Let 𝐷 : {0, 1} 𝑚 → {0, 1} be any function
that 𝜖-avoids 𝐻. Then, the following hold.
1. If 𝐺 𝑓 is a HSG construction with error parameter 𝜖, then (ℰ vs ℛ 𝐷 )𝑁 ∈ AND2𝑠 ◦ NOT ◦ 𝐷 ◦ ℭ.
2. If 𝐺 𝑓 is a PRG construction with error parameter 𝜖/2, then (ℰ vs ℛ 𝐷 )𝑁 ∈ AND𝑂(𝑁/𝜖) ◦ NOT ◦𝐷◦ℭ.
Proof. Let 𝐺 (-) be a HSG construction with error parameter 𝜖. We first present a randomized
circuit for solving (ℰ vs ℛ 𝐷 ) on inputs of length 𝑁. Let 𝑓 : {0, 1} 𝑛 → {0, 1} denote an input.
Consider a circuit 𝐷1 such that 𝐷1 ( 𝑓 ; 𝑧) := 𝐷 𝐺 𝑓 (𝑧) , where 𝑧 is an auxiliary input (that will
be regarded as non-deterministic bits or random bits). We claim that 𝐷1 can solve (ℰ vs 𝒟)
co-nondeterministically.
Claim 4.14.
1. If 𝑓 ∈ ℰ, then 𝐷1 ( 𝑓 ; 𝑧) = 0 for every 𝑧 ∈ {0, 1} 𝑠 .
2. If 𝑓 ∉ ℛ 𝐷 , then 𝐷1 ( 𝑓 ; 𝑧) = 1 for some 𝑧 ∈ {0, 1} 𝑠 .
Suppose that 𝑓 is a Yes instance of (ℰ vs 𝒟), that is, 𝑓 ∈ ℰ. By the assumption, we have
𝐺 𝑓 (𝑧) ∈ Im(𝐻). Therefore, by the property 𝐷, 𝐷 𝑓 𝑧) 𝐷 𝐺 𝑓 (𝑧) = 0.
of we obtain 1 ( ; =
Conversely, suppose that 𝐷 𝐺 𝑓 (𝑧) = 0 for every 𝑧 ∈ {0, 1} 𝑠 . This means that 𝐷 𝜖-avoids 𝐺 𝑓 .
By the reconstruction property of 𝐺 𝑓 , we 𝐷
obtain 𝑓 ∈ ℛ . Taking its contrapositive, it follows
that if 𝑓 ∉ ℛ then 𝐷1 ( 𝑓 ; 𝑧) = 𝐷 𝐺 (𝑧) = 1 for some 𝑧 ∈ {0, 1} 𝑠 . This completes the proof of
𝐷 𝑓
Claim 4.14.
Now consider a circuit 𝐷2 defined as 𝐷2 ( 𝑓 ) := 𝑧∈{0,1} 𝑠 ¬𝐷1 ( 𝑓 ; 𝑧). Then, it follows from
Ó
Claim 4.14 that the circuit 𝐷2 solves (ℰ vs ℛ 𝐷 ) on inputs of length 𝑁.
We move on to the case when 𝐺 (-) is a PRG construction. In this case, we claim that the second
item of Claim 4.14 can be strengthened to the following: If 𝑓 ∉ ℛ 𝐷 , then Pr𝑧∼{0,1} 𝑠 [𝐷1 ( 𝑓 ; 𝑧) = 1] ≥
𝜖
2.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 36
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
We prove the contrapositive of this claim. Assume that Pr𝑧∼{0,1} 𝑠 [𝐷1 ( 𝑓 ; 𝑧) = 1] < 2𝜖 . Since
𝐷 𝜖-avoids 𝐻, we have Pr𝑤∼{0,1}𝑚 [𝐷(𝑤) = 1] ≥ 𝜖. Therefore, 𝐷 2𝜖 -distinguishes 𝐺 𝑓 (-) from the
uniform distribution; by the reconstruction of 𝐺(-) , we obtain 𝑓 ∈ ℛ 𝐷 , as desired.
Therefore, 𝐷1 (-; 𝑧) is a one-sided-error randomized circuit that computes (ℰ vs ℛ 𝐷 ) with
Ó𝑘
probability at least 𝜖/2. Now define a randomized circuit 𝐷20 such that 𝐷20 ( 𝑓 ) := 𝑖=1 ¬𝐷1 ( 𝑓 ; 𝑧 𝑖 ),
where 𝑧 1 , · · · , 𝑧 𝑘 ∼ {0, 1} 𝑠 are chosen independently and 𝑘 is a parameter chosen later. Then, it
is easy to see that 𝐷20 ( 𝑓 ) = 1 for any 𝑓 ∈ ℰ; on the other hand, for any 𝑓 ∉ ℛ 𝐷 , 𝐷20 ( 𝑓 ) = 1 with
probability at most (1 − 𝜖/2) 𝑘 , which is less than 2−𝑁 by choosing 𝑘 = 𝑂(𝑁/𝜖) large enough. By
using a union bound, one can hardwire random bits in 𝐷20 as in Adleman’s trick [1], and obtain
a deterministic AND ◦ NOT ◦ 𝐷 ◦ ℭ circuit that computes (ℰ vs ℛ 𝐷 ).
4.5 The Nisan–Wigderson generator
The pseudorandom generator construction of Nisan and Wigderson [56] is particularly efficient.
Indeed, each output bit of the Nisan–Wigderson generator depends on only 1 bit of the truth
table of a candidate hard function.
Theorem 4.15 (Nisan–Wigderson Pseudorandom Generator Construction). For every constant
𝛾 > 0 and any ℓ , 𝑚 ∈ ℕ , there exists a ℭ-pseudorandom generator construction 𝐺 (-) : {0, 1} 𝑑 → {0, 1} 𝑚
with ℛ-reconstruction and error parameter 𝜖 that takes a function 𝑓 : {0, 1}ℓ → {0, 1} such that
• 𝑑 = 𝑂(ℓ ), 𝑚 ≤ 2ℓ ,
• ℭ = NC01 , and
• ℛ𝐷 = 𝐷
◦ AC02 (𝑚 · 2𝛾ℓ ; 12 − 𝑚𝜖 ).
Moreover, the output 𝐺 𝑓 (𝑧) of the PRG can be computed in space 𝑂(ℓ ) given a function 𝑓 and a seed 𝑧 as
input.
We first recall the construction of the Nisan–Wigderson generator. In order to have a
space-efficient algorithm for computing the Nisan–Wigderson generator, we use the following
construction of a combinatorial design.
Lemma 4.16 (Klivans and van Melkebeek [48], Viola [76]). For every constant 𝛾 > 0, for any ℓ ∈ ℕ ,
there exist ℓ -sized subsets 𝑆1 , · · · , 𝑆2ℓ of [𝑑] for some 𝑑 = 𝑂(ℓ ) such that
1. |𝑆 𝑖 ∩ 𝑆 𝑗 | ≤ 𝛾 · ℓ for every distinct 𝑖, 𝑗 ∈ [2ℓ ], and
2. 𝑆1 , · · · , 𝑆2ℓ can be constructed in space 𝑂(ℓ ).
A nearly disjoint generator ND is defined based on the design.
Definition 4.17. For a string 𝑧 ∈ {0, 1} 𝑑 and a subset 𝑆 ⊆ [𝑑] of indices, 𝑧 𝑆 denotes the string
obtained by concatenating the 𝑖th bit 𝑧 𝑖 of 𝑧 for every 𝑖 ∈ 𝑆. For ℓ -sized subsets 𝒮 = {𝑆1 , · · · , 𝑆𝑚 }
of [𝑑], define a nearly disjoint generator ND : {0, 1} 𝑑 → ({0, 1}ℓ )𝑚 as ND(𝑧) := (𝑧 𝑆1 , · · · , 𝑧 𝑆𝑚 ) for
every 𝑧 ∈ {0, 1} 𝑑 .
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 37
S HUICHI H IRAHARA
Using the nearly disjoint generator, the Nisan–Wigderson generator is defined as follows.
Definition 4.18 (Nisan–Wigderson generator [56]). For a Boolean function 𝑓 : {0, 1}ℓ → {0, 1}
and for ℓ -sized subsets 𝒮 = {𝑆1 , · · · , 𝑆𝑚 } of [𝑑], the Nisan–Wigderson generator NW 𝑓 : {0, 1} 𝑑 →
{0, 1} 𝑚 is defined as
NW 𝑓 (𝑧) := 𝑓 𝑚 ◦ ND(𝑧) = 𝑓 (𝑧 𝑆1 ) · · · 𝑓 (𝑧 𝑆𝑚 ).
It was shown in [56] that the pseudorandom generator construction is secure in the following
sense.
Lemma 4.19 (Security of the Nisan–Wigderson Generator [56]). For any functions 𝑇 : {0, 1} 𝑚 →
{0, 1} and 𝑓 : {0, 1}ℓ → {0, 1}, for any 𝜖 > 0, if
𝑇(NW 𝑓 (𝑧)) = 1 ≥ 𝜖,
Pr [𝑇(𝑤) = 1] − Pr
𝑤∼{0,1} 𝑚 𝑧∼{0,1} 𝑑
then there exists a one-query depth-2 oracle circuit 𝐶 𝑇 ∈ 𝑇 ◦ AC02 of size 𝑂(𝑚 · 2𝛾ℓ ) such that
1 𝜖
𝐶 𝑇 (𝑥) = 𝑓 (𝑥) ≥ + .
Pr
𝑥∼{0,1}ℓ 2 𝑚
Proof of Theorem 4.15. We use the Nisan–Wigderson generator NW(-) defined in Definition 4.18
(i. e., we define 𝐺(-) := NW(-) ). NW(-) is an NC01 -PRG construction because each bit of NW 𝑓 (𝑧)
for any fixed seed 𝑧 is equal to one bit of the truth table of 𝑓 . The ℛ-reconstruction property of
NW(-) follows from Lemma 4.19.
4.6 Meta-computational view of the Nisan–Wigderson generator
Using the Nisan–Wigderson generator construction, we present a general connection between the
existence of hitting set generators and lower bounds for meta-computational circuit lower-bound
problems. We consider any family of circuits that is closed under taking projections in the
following sense.
Definition 4.20. A class ℭ of circuits is said to be closed under taking projections if, for any 𝑠 ∈ ℕ , for
every size-𝑠 circuit 𝐶 ∈ ℭ of 𝑛 inputs, a circuit 𝐶 0 defined as 𝐶 0(𝑥 1 , · · · , 𝑥 𝑛 ) = 𝐶(𝑥 𝜎(1) , · · · , 𝑥 𝜎(𝑛) )
for some function 𝜎 : [𝑛] → [𝑛] can be simulated by a size-𝑠 ℭ-circuit.
Theorem 4.21. Let ℭ be any circuit class that is closed under taking projections. Suppose that
(E vs ℭ ◦ AC02 (2𝛼𝑛 ; 12 − 2−𝛼𝑛 )) ∉ i.o.AND ◦ NOT ◦ ℭ(𝑁 1+𝛽 ) for some constants 𝛼, 𝛽 > 0. Then, there
exists a hitting set generator 𝐺 = {𝐺 𝑛 : {0, 1} 𝑂(log 𝑛) → {0, 1} 𝑛 } 𝑛∈ℕ computable in time 𝑛 𝑂(1) and
secure against linear-size ℭ circuits.
Proof. We prove the contrapositive. Assume that, for every function 𝑠(𝑚) = 𝑂(log 𝑚), there
𝑠
exists a linear-size ℭ circuit 𝐷 that avoids the universal hitting set generator Ht𝑚 for infinitely
many 𝑚 ∈ ℕ . Given arbitrary constants 𝑐, 𝛼, 𝛽 > 0, we will choose a small constant 𝛾 > 0, and
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 38
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
𝑠
define 𝑠(𝑚) := 𝑐 0 log 𝑚/𝛾 for some large constant 𝑐 0. Then using 𝐷 that avoids Ht𝑚 , we present
a AND ◦ NOT ◦ ℭ-circuit of size 𝑁 1+𝛽 that solves the E𝑐 vs ℭ
◦ AC02 (2𝛼𝑛 ; 12 − 2−𝛼𝑛 ) Problem.
Let 𝑓 : {0, 1} 𝑛 → {0, 1} denote the input of the MCLP. We use the Nisan–Wigderson generator
construction NW 𝑓 : {0, 1} 𝑑 → {0, 1} 𝑚 of Theorem 4.15, where 𝑑 = 𝑂(𝑛), 𝑚 = 2𝛾𝑛 , and 𝜖 := 14 . By
Theorem 4.15, this is a black-box NC01 -PRG construction with AC
g0 (22𝛾𝑛 ; 1 − 1 ) reconstruction.
2 2 4𝑚
In order to apply Theorem 4.13, we claim that NW 𝑓 (𝑧) ∈ Im(Ht𝑚 𝑠
) for every 𝑓 ∈ E𝑐 and every
𝑧 ∈ {0, 1} 𝑑 . By Theorem 4.15, the output NW 𝑓 (𝑧) can be described by using a seed 𝑧 and a
description for 𝑓 in time 𝑁 𝑂(1) , and thus
Kt(NW 𝑓 (𝑧)) ≤ |𝑧| + Kt( 𝑓 ) + 𝑂(log 𝑁) = 𝑂(𝑛).
In particular, for a large enough constant 𝑐 0, we have
Kt(NW 𝑓 (𝑧)) ≤ 𝑐 0 𝑛 = 𝑠(𝑚).
𝑠
By the universality of Ht𝑚 (Proposition 4.3) we obtain that NW 𝑓 (𝑧) ∈ Im(Ht𝑚
𝑠
).
By applying Theorem 4.13, we have (E𝑐 vs 𝐷
◦ AC02 (22𝛾𝑛 ; 12 − 4𝑚
1
))𝑁 ∈ AND𝑂(𝑁) ◦ NOT ◦ 𝐷 ◦ NC01 .
Since 𝐷 is a ℭ-circuit of size 𝑚 = 2𝛾𝑛 , it follows that (E𝑐 vs ℭ
◦ AC02 (2𝑂(𝛾𝑛) ; 12 − 4𝑚
1
))𝑁 ∈ AND ◦
NOT ◦ ℭ(𝑂(𝑁 1+𝛾 )). Note that this holds for infinitely many 𝑁 = 𝑚 . By choosing 𝛾 small
1/𝛾
enough depending on 𝛼, 𝛽, the result follows.
We observe that the converse direction also holds. In particular, for any circuit class
ℭ ⊆ P/poly such that ℭ is closed under taking projections and AND ◦ NOT ◦ ℭ = ℭ, our reductions
in fact establish the equivalence between the existence of a hitting set generator secure against ℭ
(2𝑜(𝑛) ; 1 − 2−𝑜(𝑛) ) Problem.
and a ℭ-lower bound for the E vs SIZE 2
Proposition 4.22 (Converse of Theorem 4.21). Let ℭ be any circuit complexity class. Suppose
that there exists a hitting set generator 𝐺 = {𝐺 𝑛 : {0, 1} 𝑂(log 𝑛) → {0, 1} 𝑛 } 𝑛∈ℕ computable in time
𝑛 𝑂(1) and secure against linear-size ℭ circuits. Then, for any constant 𝑘 ∈ ℕ, for all sufficiently
large 𝑁 ∈ ℕ , no NOT ◦ ℭ circuit of size 𝑁 𝑘 can solve E vs SIZE
(2𝛼𝑛 ; 1 − 2−𝛼𝑛 )
2 for 𝛼 := 1/4 nor
𝑁
MKtP[𝑂(log 𝑁), 𝑁 − 1] on input length 𝑁.
(2𝛼𝑛 ; 1 − 2−𝛼𝑛 ))
Proof. We first observe that MKtP[𝑂(log 𝑁), 𝑁 − 1] is reducible to (E vs SIZE 2
(2𝛼𝑛 ; 1 − 2−𝛼𝑛 ). Since the truth table of 𝑓 can
via an identity map: Take any function 𝑓 ∈ SIZE 2
𝑁
be described by a circuit of size 𝑁 𝛼 and log ≤𝑁/2−𝑁 1−𝛼 bits of information in time 𝑁
𝑂(1) , the
Kt-complexity of tt( 𝑓 ) is at most
e 𝛼 ) + 𝑁 · H2 (1/2 − 𝑁 −𝛼 ) + 𝑂(log 𝑁) ≤ 𝑁 − Ω(𝑁 1−2𝛼 ),
𝑂(𝑁
which is much smaller than 𝑁 − 1. Therefore, it suffices to prove the result only for
MKtP[𝑂(log 𝑁), 𝑁 − 1].
We prove the contrapositive. Suppose that, for some constant 𝑘 ∈ ℕ , for any constant 𝑐, for
infinitely many 𝑁 ∈ ℕ , there exists a NOT ◦ ℭ circuit of size 𝑁 𝑘 that solves the promise problem
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 39
S HUICHI H IRAHARA
MKtP[𝑐 log 𝑁 , 𝑁 − 1]. Consider any family of functions 𝐺 = {𝐺 𝑚 : {0, 1} 𝑑 log 𝑚 → {0, 1} 𝑚 } 𝑚∈ℕ
computable in time 𝑚 𝑑 for a constant 𝑑. Let 𝑐 := 4𝑘𝑑, and take a NOT ◦ ℭ circuit ¬𝐶 of size 𝑁 𝑘
that solves MKtP[𝑐 log 𝑁 , 𝑁 − 1] on inputs of length 𝑁.
We regard 𝐶 as a circuit that takes 𝑚 := 𝑁 𝑘 input bits by ignoring 𝑚 − 𝑁 input bits, and in
what follows we claim that the linear-size circuit 𝐶 avoids 𝐺 𝑚 . For a string 𝑤 ∈ {0, 1} 𝑚 , denote
by 𝑤 𝑁 the first 𝑁 bits of 𝑤.
Let 𝑧 ∈ {0, 1} 𝑑 log 𝑚 be any seed of 𝐺 𝑚 . Since 𝐺 𝑚 (𝑧) 𝑁 can be described by 𝑁 ∈ ℕ and
𝑧 ∈ {0, 1} 𝑑 log 𝑚 in time 𝑚 𝑑 , its Kt complexity is
Kt(𝐺 𝑚 (𝑧) 𝑁 ) ≤ log 𝑁 + |𝑧| + 𝑑 log 𝑚 + 𝑜(log 𝑚) ≤ 4𝑘𝑑 log 𝑁 ,
which means that 𝐺 𝑚 (𝑧) 𝑁 is a Yes instance of MKtP[𝑐 log 𝑁 , 𝑁 − 1] and thus 𝐺 𝑚 (𝑧) is rejected
by 𝐶.
Now consider a string 𝑤 ∼ {0, 1} 𝑚 chosen uniformly at random. By a standard counting
argument, Kt(𝑤 𝑁 ) ≥ 𝑁 − 1 with probability at least 12 ; thus 𝐶 accepts at least a half of all
inputs. Therefore, the function 𝐺 𝑚 is not secure against 𝐶.
Applying Theorem 4.21 to depth-𝑑 circuits ℭ := AC0𝑑 , we obtain the following.
Corollary 4.23. Let 𝑑 be a constant. Suppose that (E vs AC 0
𝑑+2
(2𝛼𝑛 ; 12 − 2−𝛼𝑛 )) ∉ i.o.AC0𝑑+1 (𝑁 1+𝛽 )
for some constants 𝛼, 𝛽 > 0. Then, there exists a hitting set generator 𝐺 = {𝐺 𝑛 : {0, 1} 𝑂(log 𝑛) →
{0, 1} 𝑛 } 𝑛∈ℕ computable in time 𝑛 𝑂(1) and secure against linear-size AC0𝑑 circuits.
This means that, in order to obtain a nearly optimal hitting set generator for AC0𝑑 , it suffices
to prove that nearly linear-size AC0𝑑+1 circuits cannot distinguish the truth tables of functions in
E/𝑂(𝑛) from the truth tables of functions that cannot be approximated by AC0𝑑+2 circuits.
We present a proof of Theorem 1.12.
Restatement of Theorem 1.12. The following are equivalent.
g0 (2𝑜(𝑛) ; 1 − 2−𝑜(𝑛) )) ∉
1. For any constants 𝑑, 𝑑0, there exists a constant 𝛽 > 0 such that (E vs AC 𝑑0 2
i.o.AC0𝑑 (𝑁 1+𝛽 ).
2. For any constant 𝑑, there exists a hitting set generator 𝐺 = {𝐺 𝑛 : {0, 1} 𝑂(log 𝑛) → {0, 1} 𝑛 } 𝑛∈ℕ
computable in time 𝑛 𝑂(1) and secure against linear-size AC0𝑑 circuits.
3. For any constant 𝑑, there exist constants 𝑐, 𝛽 > 0 such that MKtP[𝑐 log 𝑁 , 𝑁 − 1] ∉
i.o.AC0𝑑 (𝑁 1+𝛽 ).
4. For any constants 𝑑, 𝑘, there exists a constant 𝑐 > 0 such that MKtP[𝑐 log 𝑁 , 𝑁 − 1] ∉
i.o.AC0𝑑 (𝑁 𝑘 ).
Proof of Theorem 1.12. Item 1 =⇒ Item 2 follows from Corollary 4.23. Item 2 =⇒ Item 4 follows
from Proposition 4.22. Item 4 =⇒ Item 3 is obvious. Item 3 =⇒ Item 1 holds because the truth
g0 (2𝑜(𝑛) ; 1 − 2−𝑜(𝑛) ) has Kt complexity less than 𝑁 − 1.
table of any function in AC
2
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 40
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
4.7 Hardness amplification and MCLPs
The main advantage of studying MCLPs is that hardness amplification can be naturally regarded
as a reduction between two different MCLPs. In this section, we present such reductions.
Impagliazzo and Wigderson [44] gave a derandomized hardness amplification theorem. We
use the following generalized version of their result.
Theorem 4.24 (Derandomized hardness amplification). Let 𝛾 > 0 be an arbitrary constant. There
exists a hardness amplification procedure Amp that takes a function 𝑓 : {0, 1} 𝑛 → {0, 1} and parameters
𝑓
𝛿, 𝜖 > 0, and returns a Boolean function Amp𝜖,𝛿 : {0, 1} 𝑂(𝑛+log(1/𝜖)) → {0, 1} satisfying the following:
𝑓
1. If size(Amp
g
𝜖,𝛿
; 1/2 − 𝜖) ≤ 𝑠, then size(
g 𝑓 ; 𝛿) ≤ 𝑠 · poly(1/𝜖, 1/𝛿).
2. For any fixed 𝑦 ∈ {0, 1} 𝑂(𝑛+log(1/𝜖)) , there exist strings 𝑣 1 , · · · , 𝑣 𝑘 ∈ {0, 1} 𝑛 for some 𝑘 =
𝑓
𝑂(log(1/𝜖)/𝛿) such that Amp𝜖,𝛿 (𝑦) = 𝑓 (𝑣 1 ) ⊕ · · · ⊕ 𝑓 (𝑣 𝑘 ). Moreover, if 𝑦 is distributed
uniformly at random, for each 𝑖 ∈ [𝑘], 𝑣 𝑖 is distributed uniformly at random.
𝑓
3. Amp𝜖,𝛿 (𝑦) can be computed in 𝑂(𝑛 + log(1/𝛿) + log(1/𝜖)) space, given 𝑓 , 𝑦, 𝜖 and 𝛿 as an input.
Theorem 4.24 slightly differs from derandomized hardness amplification theorems of [44, 31]
in that we are also interested in the case when the hardness parameter 𝛿 is 𝑜(1), which is not
required in a standard application of derandomized hardness amplification theorems. We defer
a proof of Theorem 4.24 to Appendix A.
Using Theorem 4.24, we give a reduction among different MCLPs.
Theorem 4.25. For any constants 𝛼, 𝛿 > 0, for all sufficiently small 𝛽 > 0, there exists a XOR𝑂(𝛽 log 𝑁) -
(2𝛼𝑛 ; 𝛿)) to (E vs SIZE
computable reduction from (E vs SIZE (2𝛽𝑛 ; 1 − 2−𝛽𝑛 )).
2
Proof. The reduction is to simply take the hardness amplification procedure Amp of Theorem 4.24.
Specifically, given the truth table of a function 𝑓 : {0, 1} 𝑛 → {0, 1}, the reduction maps 𝑓 to
𝑓
the truth table of Amp𝜖,𝛿 : {0, 1} 𝑛 → {0, 1}, where 𝜖 := 2−𝛽𝑛 and 𝑛 0 = 𝑂(𝑛). By the second
0
item of Theorem 4.24, each output of the reduction is computable by a XOR of 𝑘 bits, where
𝑘 = 𝑂(log(1/𝜖)/𝛿) = 𝑂(𝛽𝑛).
We claim the correctness of the reduction. Suppose that Kt( 𝑓 ) ≤ 𝑂(log 𝑁). Then, by the
𝑓
third item of Theorem 4.24, we obtain that Kt(Amp𝜖,𝛿 ) ≤ 𝑂(log 𝑁).
Conversely, suppose that 𝑓 ∉ SIZE (2𝛼𝑛 ; 𝛿); that is, size(
g 𝑓 ; 𝛿) > 2𝛼𝑛 > 2𝛽𝑛 · poly(1/𝜖, 1/𝛿),
where the last inequality holds by choosing 𝛽 > 0 small enough. By the first item of Theorem 4.24,
𝑓 𝑓
we obtain that size(Amp
g ; 1 − 2−𝛽𝑛 ) > 2𝛽𝑛 , which implies that Amp𝜖,𝛿 ∉ SIZE
𝜖,𝛿 2
(2𝛽0 𝑛0 ; 1 − 2−𝛽0 𝑛0 )
2
for some constant 𝛽0 > 0.
Applying the reduction of Theorem 4.25 to Corollary 4.23, we obtain the following.
Corollary 4.26. Let 𝑑 ∈ ℕ , 𝛿 > 0 be constants. Suppose that (E vs SIZE (2𝛼𝑛 ; 𝛿)) ∉ i.o.AC0 (𝑁 1+𝛽 )
𝑑+2
for some constants 𝛼, 𝛽 > 0. Then, there exists a hitting set generator 𝐺 = {𝐺 𝑛 : {0, 1} 𝑂(log 𝑛) →
{0, 1} 𝑛 } 𝑛∈ℕ computable in time 𝑛 𝑂(1) and secure against linear-size AC0𝑑 circuits.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 41
S HUICHI H IRAHARA
Proof. We prove the contrapositive. Under the assumption that no hitting set generator is secure
against AC0𝑑 , it follows from Corollary 4.23 that (E vs AC
0
𝑑+2
(2𝛽𝑛 ; 21 − 2−𝛽𝑛 )) ∈ i.o.AC0𝑑+1 (𝑁 1+𝛾 ) for
any constants 𝛽, 𝛾 > 0. Our goal is to prove that (E vs SIZE (2𝛼𝑛 ; 𝛿)) ∈ i.o.AC0 (𝑁 1+𝜂 ) for any
𝑑+2
constants 𝛼, 𝜂 > 0.
Fix any constants 𝛼, 𝜂 > 0. By Theorem 4.25, there exists a XOR𝑂(𝛽𝑛) -computable reduction
(2𝛼𝑛 ; 𝛿)) to (E vs AC
from (E vs SIZE 0
(2𝛽𝑛 ; 12 − 2−𝛽𝑛 )), for all sufficiently small 𝛽 > 0. The
𝑑+2
latter problem can be solved by an AC𝑑+1 (𝑁 1+𝛾 ). Thus we obtain an AC0𝑑+1 (𝑁 1+𝛾 ) ◦ XOR𝑂(𝛽𝑛)
0
circuit that computes the former problem. Since XOR𝑂(𝛽𝑛) can be computed by a depth-2
circuit of size 𝑁 𝑂(𝛽) , by merging one bottom layer of the AC0𝑑+1 circuit, we obtain a circuit in
(2𝛼𝑛 ; 𝛿)). The result follows by choosing 𝛽, 𝛾 > 0
AC0𝑑+2 (𝑁 1+𝛾+𝑂(𝛽) ) that computes (E vs SIZE
small enough depending on 𝜂 > 0.
Note that AC0 circuits are not capable of computing XOR gates of large fan-in. If a
computational model can compute XOR gates, it is possible to compute a locally-decodable
error-correcting code. Specifically, we provide an efficient reduction from (E vs SIZE(2𝑜(𝑛) )) to
(2𝑜(𝑛) ; 1 − 2−𝑜(𝑛) )) that is computable by a single layer of XOR gates.
(E vs SIZE 2
Theorem 4.27 (Reductions by Error-Correcting Codes). For any constants 𝛼, 𝛾 > 0, for all
sufficiently small 𝛽 > 0, there exists a reduction from (E vs SIZE(2𝛼𝑛 )) to (E vs SIZE
(2𝛽𝑛 ; 1 − 2−𝛽𝑛 ))
2
that is computable by one layer of 𝑂(𝑁 ) XOR gates.
1+𝛾
Lemma 4.28 (see [68, 74, 78]). For any small constant 𝛽 > 0, for all large 𝑛 ∈ ℕ , there ex-
ists an error-correcting
√ code Enc 𝑓 that encodes a function 𝑓 : {0, 1} 𝑛 → {0, 1} as a function
𝛽))𝑛
Enc 𝑓 : {0, 1}(1+𝑂( → {0, 1} satisfying following:
√
1. size( 𝑓 ) ≤ size(Enc
g ; 2 − 2−𝛽𝑛 ) · 2𝑂( 𝛽𝑛) .
𝑓 1
√
2. For any fixed 𝑦 ∈ {0, 1}(1+𝑂( 𝛽))𝑛 , Enc 𝑓 (𝑦) can be computed by an XOR of some bits of the truth
table of 𝑓 .
3. Enc 𝑓 can be computed in time 2𝑂(𝑛) .
Proof Sketch. We use a Reed–Muller code concatenated with a Hadamard code. The crux
is that the length of a codeword of can be made small because the query complexity of
local-list-decoding algorithms is allowed to be quite large.
Let 𝑓 : {0, 1} 𝑛 → {0, 1}. Let 𝔽 𝑞 be a finite field, where 𝑞 = 2 𝑘 for some 𝑘. Pick 𝐻 ⊆ 𝔽 𝑞 , and
encode any element of {0, 1} 𝑛 as an element of 𝐻 𝑡 by taking an injection 𝜂 from {0, 1} 𝑛 to 𝐻 𝑡 ,
where 𝑡 is some large constant chosen later. Let the size |𝐻 | of 𝐻 be 2𝑛/𝑡 . Any 𝑓 : {0, 1} 𝑛 → {0, 1}
can be encoded as a low-degree extension b 𝑓 : 𝔽 𝑞𝑡 → 𝔽 𝑞 such that b
𝑓 and 𝑓 ◦ 𝜂−1 agree on 𝐻 𝑡 .
𝑓 can be defined as
Specifically, b
Õ 𝑡
Ö
𝑓 (𝑥) =
b 𝑓 (𝜂−1 (𝑦)) 𝛿 𝑦𝑖 (𝑥 𝑖 )
𝑦∈𝐻 𝑡 𝑖=1
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 42
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
for 𝑥 = (𝑥 1 , . . . , 𝑥 𝑡 ) ∈ 𝔽 𝑞𝑡 , where 𝛿 𝑎 is a polynomial of degree at most |𝐻 | such that 𝛿 𝑎 (𝑎) = 1 and
𝑓 is at most 𝑑 := 𝑡 |𝐻 | = 𝑡2𝑛/𝑡 . We will set
𝛿 𝑎 (𝑏) = 0 for every 𝑏 ∈ 𝐻 \ {𝑎}. The total degree of b
𝑞 = 𝑡2 𝑛/𝑡+𝑂(𝛽𝑛) .
Then, each alphabet b 𝑓 (𝑥) in the Reed–Muller code is encoded with a Hadamard code.
𝑓
Namely, Enc (𝑥, 𝑦) := h 𝑓 (𝑥), 𝑦i, where 𝑥 ∈ 𝔽 𝑞𝑡 , 𝑦 ∈ 𝔽 2𝑘 and h-, -i denotes the inner product
b
𝑓 𝑡+1 = 𝑂(𝑡 𝑡+1 2(𝑛/𝑡+𝑂(𝛽𝑛))(𝑡+1) ).
√ Enc is at most 𝑞
function over 𝔽 2 . The length of the truth table of
𝛽))·𝑛
By choosing 𝑡 := 1/ 𝛽, this is bounded by 2(1+𝑂(
p
. The second item holds because for every
𝑓 (𝑥) ∈ 𝔽 𝑞 𝔽 𝑘 can be written as an XOR of some bits of the truth
fixed 𝑥, each coordinate of b 2
table of 𝑓 .14
To see the first item, we use the local list decoding algorithm of Sudan, Trevisan, and
Vadhan [68]. They gave a local
list-decoding
algorithm for the code Enc 𝑓 running in time
poly(𝑡, 𝑞) that can handle a 1
2 − (𝑑/𝑞)
Ω(1) -fraction of errors, which is more than 12 − 2−𝛽𝑛 by
choosing 𝑞 := 𝑡2𝑛/𝑡+𝑂(𝛽𝑛) large enough. Given a circuit that approximates Enc 𝑓 on a 12 − 2−𝛽𝑛
fraction of inputs, one can apply the local list-decoding algorithm to obtain
√ a circuit that
computes 𝑓 on every input; thus we have size( 𝑓 ) ≤ size(Enc
g ; 2 − 2−𝛽𝑛 ) · 2𝑂(
𝑓 1 𝛽)𝑛
.
Proof of Theorem 4.27. We apply the error-correcting code Enc of Theorem 4.27. Specifically,
𝑓
given 𝑓 : {0, 1} 𝑛 → {0, 1} 𝑛0
√ as input, we map 𝑓 to Enc : {0, 1} → {0, 1}. Since the length of
tt(Enc 𝑓 ) is 2𝑛 = 𝑁 1+𝑂( 𝛽) and each bit is computable by a XOR of some bits of tt( 𝑓 ), the
0
reduction is computable by one layer of 𝑂(𝑁 1+𝛾 ) XOR gates for all sufficiently small 𝛽 > 0.
We claim the correctness of the reduction. Suppose that Kt( 𝑓 ) = 𝑂(log 𝑁); then, by the third
item of Lemma 4.28, we have Kt(Enc 𝑓 ) = 𝑂(log 𝑁).
Now suppose that 𝑓 ∉ SIZE(2𝛼𝑛 ). By Lemma 4.28, we have
1 √
g − 2−𝛽𝑛 ) · 2𝑂( 𝛽𝑛) .
2𝛼𝑛 < size( 𝑓 ) ≤ size(Enc 𝑓
;
2
√
Therefore, we obtain that size(Enc
g ; 2 − 2−𝛽𝑛 ) > 2(𝛼−𝑂( 𝛽))𝑛 ≥ 2𝛽𝑛 , where the last inequality
𝑓 1
holds by choosing 𝛽 > 0 small enough. Therefore, Enc 𝑓 ∉ SIZE
(2𝛽0 𝑛0 ; 1 − 2−𝛽0 𝑛0 ) holds for some
2
constant 𝛽0 > 0.
Applying the reduction, we obtain the following.
Theorem 4.29. Let 𝑑 be a constant. Suppose that (E vs SIZE(2𝛼𝑛 )) ∉ i.o.AC0𝑑+1 ◦ XOR(𝑁 1+𝛽 ) for some
constants 𝛼, 𝛽 > 0. Then, there exists a hitting set generator 𝐺 = {𝐺 𝑛 : {0, 1} 𝑂(log 𝑛) → {0, 1} 𝑛 } 𝑛∈ℕ
computable in time 𝑛 𝑂(1) and secure against linear-size AC0𝑑 ◦ XOR circuits.
Proof. We prove the contrapositive. Let 𝛼, 𝛽 > 0 be arbitrary constants. Assuming that no hitting
(2𝛼0 𝑛 ; 1 − 2−𝛼0 𝑛 )) ∈
set generator is secure against AC0𝑑 ◦ XOR, by Theorem 4.21, we have (E vs SIZE 2
i.o.AC𝑑+1 ◦XOR(𝑁 0 ) for any constants 𝛼 0 , 𝛽 0 > 0. By Theorem 4.27, (E vs SIZE(2𝛼𝑛 )) is reducible
0 1+𝛽
14Note that an addition over 𝔽 𝑞 is given by a coordinate-wise addition over 𝔽 2𝑘 .
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 43
S HUICHI H IRAHARA
(2𝛼0 𝑛 ; 1 − 2−𝛼0 𝑛 )) by one layer of 𝑂(𝑁 1+𝛾 ) XOR gates for any constant 𝛾 > 0 and any
to (E vs SIZE 2
small enough constant 𝛼0 > 0. Therefore, we obtain a circuit in i.o.AC0𝑑+1 ◦ XOR ◦ XOR((𝑁 1+𝛾 )1+𝛽0 )
that computes (E vs SIZE(2𝛼𝑛 )). By merging the bottom two XOR layers, the circuit can be
written as an i.o.AC0𝑑+1 ◦ XOR circuit of size 𝑁 1+𝛾+𝛽0 +𝛾𝛽0 .15 The result follows by choosing positive
constants 𝛾, 𝛽0 𝛽 small enough.
We are now ready to complete a proof of Theorem 1.11, which establishes the equivalence
between the existence of a hitting set generator secure against AC0 ◦ XOR and the AC0 ◦ XOR
circuit lower bound for the E vs SIZE(2𝑜(𝑛) ) Problem.
Restatement of Theorem 1.11. The following are equivalent.
1. For any constant 𝑑, there exists a hitting set generator 𝐺 = {𝐺 𝑛 : {0, 1} 𝑂(log 𝑛) → {0, 1} 𝑛 } 𝑛∈ℕ
computable in time 𝑛 𝑂(1) and secure against linear-size AC0𝑑 ◦ XOR circuits.
2. For any constant 𝑑, for some constant 𝛽 > 0, (E vs SIZE(2𝑜(𝑛) )) ∉ i.o.AC0𝑑 (𝑁 1+𝛽 ).
3. For any constant 𝑑, for some constant 𝛽 > 0, MKtP[𝑂(log 𝑁), 𝑁 𝑜(1) ] ∉ i.o.AC0𝑑 ◦ XOR(𝑁 1+𝛽 ).
4. For any constants 𝑑, 𝑘 ∈ ℕ , MKtP[𝑂(log 𝑁), 𝑁 𝑜(1) ] ∉ i.o.AC0𝑑 ◦ XOR(𝑁 𝑘 ).
Proof of Theorem 1.11. The implications from Item 4 to Item 3 and from Item 3 to Item 2 are
trivial. The implication from Item 2 to Item 1 immediately follows from Theorem 4.29. The
implication from Item 1 to Item 4 is a standard approach for showing a lower bound for MKtP,
and follows from Proposition 4.22.
4.8 KS complexity and read-once branching program
We now turn our attention to KS complexity. This amounts to considering a hitting set generator
that is computable in a limited amount of space. Applying our proof ideas to the case of
read-once branching programs, we provide a potential approach for resolving BPL = L.
Restatement of Theorem 1.13. There exists a universal constant 𝜌 > 0 satisfying the following.
(2𝛼𝑛 ; 2−𝜌𝛼𝑛 )) cannot be computed
Suppose that, for some constants 𝛼, 𝛽 > 0, (DSPACE(𝑛) vs SIZE
by a read-once co-nondeterministic branching program of size 𝑁 1+𝛽 for all large input length
𝑁 ∈ ℕ . Then there exists a hitting set generator 𝐺 = {𝐺 𝑛 : {0, 1} 𝑂(log 𝑛) → {0, 1} 𝑛 } 𝑛∈ℕ
computable in 𝑂(log 𝑛) space and secure against linear-size read-once branching programs.
Since the class of read-once branching programs is not closed under taking several reductions
presented so far, we provide a self-contained proof below.
15Recall that we count the number of gates except for input gates.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 44
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
Proof. We prove the contrapositive of Theorem 1.13 for the universal hitting set generator HS.
Assume that, for every function 𝑠(𝑚) = 𝑂(log 𝑚), there exists a linear-size read-once branching
𝑠
program 𝐷 that avoids HS𝑚 for infinitely many 𝑚 ∈ ℕ . Given arbitrary constants 𝑐, 𝛼, 𝛽 > 0,
we will choose a small constant 𝛾 > 0, and define 𝑠(𝑚) := 𝑐 0 log 𝑚/𝛾 for some large constant
𝑠
𝑐 0. Then using 𝐷 that avoids HS𝑚 , we present a coRP-type randomized read-once branching
program that solves (ΠYes , ΠNo ) := (DSPACE(𝑐𝑛)/𝑛 𝑐𝑛 vs SIZE (2𝛼𝑛 ; 2−𝜌𝛼𝑛 )) on inputs of length
𝑛
𝑁 = 2 , for some sufficiently large 𝑁 := 𝑚 . Here, a randomized branching program means a
1/𝛾
probability distribution on branching programs.
For simplicity, we first explain a construction of a branching program that may not be
read-once. A randomized branching program 𝐷0 is defined as follows. Given an input
𝑓
𝑓 : {0, 1} 𝑛 → {0, 1}, set 𝜖 := 1/4𝑚. Define e 𝑓 := Amp𝜖,𝛿 : {0, 1} 𝑂(log 𝑁) → {0, 1}. Let ℓ denote
𝑓 , and let 𝑑 = 𝑂(ℓ ) = 𝑂(𝑛) denote the seed length of the Nisan–Wigderson
the input length of e
generator instantiated with ℓ -sized 𝑚 subsets (Definition 4.18). Pick 𝑧 ∼ {0, 1} 𝑑 and output
¬𝐷(NW 𝑓 (𝑧)). This is a randomized branching program because for each fixed 𝑧, each bit of
e
NW 𝑓 (𝑧) is equal to e
𝑓 (𝑧 𝑆 ) for some subset 𝑆, and hence by Item 2 of Theorem 4.24 it is some linear
e
combination of at most 𝑘 bits of tt( 𝑓 ), which can be computed by a read-once width-2 branching
program of size 𝑂(𝑘).16 Thus ¬𝐷(NW 𝑓 (𝑧)) can be implemented as a branching program of
e
size 𝑂(𝑚 · 𝑘), by replacing each node of 𝐷 by the read-once width-2 branching programs that
compute some linear combinations of tt( 𝑓 ).
We claim the correctness of the randomized branching program 𝐷0 .
Claim 4.30.
1. 𝐷0 accepts every 𝑓 ∈ ΠYes with probability 1.
2. For every 𝑓 ∈ ΠNo , the probability that 𝐷0 rejects 𝑓 is at least 14 .
3. The size of 𝐷0 is at most 𝑁 𝛽 .
Take any Yes instance 𝑓 ∈ ΠYes . We observe that the output NW 𝑓 (𝑧) of the generator has
e
small KS complexity. Indeed,
KS(NW 𝑓 (𝑧)) ≤ |𝑧| + KS( e
𝑓 ) + 𝑂(log 𝑁) ≤ KS( 𝑓 ) + 𝑂(log 𝑁),
e
where we used Lemma 4.16 and Item 3 of Theorem 4.24. In particular, for a large enough
constant 𝑐 0, we have
KS( 𝑓 ) ≤ 𝑐 0 log 𝑁 = 𝑠(𝑚),
and thus 𝐷(NW 𝑓 (𝑧)) = 0 by Proposition 4.6 and the assumption that 𝐷 avoids HS𝑚
𝑠
. This means
e
that the algorithm 𝐷0 accepts for every choice of 𝑧.
16Note that, since 𝑧 is fixed, the branching program does not have to compute 𝑧 𝑆 from 𝑧.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 45
S HUICHI H IRAHARA
Conversely, suppose that the algorithm 𝐷0 accepts some input 𝑓 with probability at least
3
4. We claim that 𝑓 ∉ ΠNo . The assumption means that Pr𝑧 [𝐷(NW 𝑓 (𝑧)) = 0] ≥ 34 , which is
e
equivalent to saying that Pr𝑧 [𝐷(NW 𝑓 (𝑧)) = 1] ≤ 14 . On the other hand, since 𝐷 avoids HS𝑚
𝑠
, we
e
1
have Pr𝑤 [𝐷(𝑤) = 1] ≥ 2 . In particular, we obtain
1
Pr[𝐷(𝑤) = 1] − Pr[𝐷(NW 𝑓 (𝑧)) = 1] ≥ .
e
𝑤 𝑧 4
By the security proof of the Nisan–Wigderson generator (Lemma 4.19), there exists a one-query
oracle circuit 𝐶 of size 𝑂(𝑚 · 2𝛾ℓ ) such that
1 1
Pr [𝐶 𝐷 (𝑦) = e
𝑓 (𝑦)] ≥ + .
𝑦∼{0,1}ℓ 2 4𝑚
Now replacing the oracle gate of 𝐶 with a circuit that simulates 𝐷, we obtain a circuit of size
𝑚 𝑂(1) + 𝑚 · 𝑁 𝑂(𝛾) . By the property of Amp𝜖,𝛿 (Item 1 of Theorem 4.24), we obtain another circuit
𝐶 0 of size 𝑚 𝑂(1) · 𝑁 𝑂(𝛾) · (1/𝛿)𝑂(1) such that
Pr [𝐶 0(𝑥) = 𝑓 (𝑥)] ≥ 1 − 𝛿.
𝑥∼{0,1} 𝑛
g 𝑓 ; 𝑁 −𝛾 ) ≤ 𝑁 𝑂(𝛾) , where 𝛾 > 0 is an arbitrary small
Choosing 𝛿 := 𝑁 −𝛾 , we obtain that size(
constant. This completes the proof of the second item of Claim 4.30, by choosing 𝛾 small enough
so that 𝑂(𝛾) < 𝛼.
Recall that the size of 𝐷0 is 𝑂(𝑚 · 𝑘). Here 𝑘 is the parameter from Theorem 4.24 and
𝑘 = 𝑂(log(1/𝜖)/𝛿) = 𝑁 𝑂(𝛾) . Thus the size of 𝐷0 is at most 𝑁 𝑂(𝛾) ≤ 𝑁 𝛽 , by choosing 𝛾 small
enough so that 𝑂(𝛾) ≤ 𝛽. This completes the proof of Claim 4.30.
Now we modify the construction of 𝐷0 in order to obtain a read-once branching program
𝐷1 . The branching program 𝐷0 (NW 𝑓 (𝑧)) may read some 𝑥-th bit of the input tt( 𝑓 ) twice
e
only if there exists a pair of distinct indices (𝑖, 𝑗) such that the 𝑖th bit of NW 𝑓 (𝑧) and the
e
𝑗th bit of NW 𝑓 (𝑧) are linear combinations of tt( 𝑓 ) that contain 𝑓 (𝑥). We say that a coin flip
e
𝑧 is bad if this happens. To ensure that a coin flip is bad with small probability, we take
a pairwise independent generator 𝐺2 : {0, 1} 𝑂(ℓ ) → ({0, 1}ℓ )𝑚 , and define a modified Nisan–
Wigderson generator NW0 𝑓 := e𝑓 𝑚 ◦ (ND ⊕ 𝐺2 ), where ND ⊕ 𝐺2 denotes the function such that
e
ND ⊕ 𝐺2 (𝑢, 𝑣) := ND(𝑢) ⊕ 𝐺2 (𝑣). Using this modified construction, the read-once branching
program 𝐷1 is defined as ¬𝐷(NW0 𝑓 (𝑧)) if 𝑧 is not bad, and otherwise defined as a trivial
e
branching program that outputs 1 always. (Note here that since we deal with a non-uniform
computation, one does not need to check the badness of 𝑧 by using a branching program.) By
the definition, it is obvious that 𝐷1 is read-once; hence it remains to claim that 𝐷1 satisfies the
promise of (ΠYes , ΠNo ).
As in the case of 𝐷0 , for 𝑓 ∈ ΠYes , it can be seen that 𝐷(NW0 𝑓 (𝑧)) = 0 for every 𝑧, and
e
hence 𝐷1 always accepts. (We note that the KS complexity increases by an additive term
of the input length of 𝐺2 , which is 𝑂(log 𝑁).) Conversely, we claim that if 𝐷1 accepts with
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 46
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
probability at least 78 , then 𝑓 ∉ ΠNo . Assume that Pr𝑧 [𝐷1 accepts] ≥ 78 . We claim that the
probability that 𝑧 is bad is small: Fix any distinct indices (𝑖, 𝑗) ∈ [𝑚]2 . Recall that by Item 2
of Theorem 4.24, there exist functions ℎ1 , · · · , ℎ 𝑘 such that e
𝑓 (𝑦) = 𝑓 (ℎ1 (𝑦)) ⊕ · · · ⊕ 𝑓 (ℎ 𝑘 (𝑦))
for every 𝑦 ∈ {0, 1}ℓ , where 𝑘 = 𝑂(log(1/𝜖)/𝛿). Then, the 𝑖th bit of NW0 𝑓 (𝑢, 𝑣) is equal to
b
𝑓 (ℎ1 (𝑢𝑆𝑖 ⊕ 𝐺2 (𝑣)𝑖 )) ⊕ · · · ⊕ 𝑓 (ℎ 𝑘 (𝑢𝑆𝑖 ⊕ 𝐺2 (𝑣)𝑖 )). Fix any distinct indices 𝑖 0 , 𝑗 0 ∈ [𝑘]. Then, we have
1
Pr [ℎ 𝑖0 (𝑢𝑆𝑖 ⊕ 𝐺2 (𝑣)𝑖 ) = ℎ 𝑗0 (𝑢𝑆 𝑗 ⊕ 𝐺2 (𝑣) 𝑗 )] = Pr [ℎ 𝑖0 (𝑢𝑆𝑖 ⊕ 𝑎) = ℎ 𝑗0 (𝑢𝑆 𝑗 ⊕ 𝑏)] = ,
𝑢,𝑣 𝑢 𝑁
𝑎,𝑏∼{0,1}ℓ
where the first inequality holds by the pairwise independence of 𝐺2 and the second inequality
holds because ℎ(𝑎) is distributed identically with the uniform distribution for 𝑎 ∼ {0, 1}ℓ . By
the union bound over all (𝑖, 𝑗) and (𝑖 0 , 𝑗 0), the probability that 𝑧 is bad is bounded above by
(𝑘𝑚)2 · 1/𝑁 ≤ 𝑁 𝑂(𝛾)−1 ≤ 81 for a sufficiently small 𝛾 > 0 and a large 𝑁 ∈ ℕ . Thus we obtain
3
Pr[𝐷(NW0 𝑓 (𝑧)) = 0] ≥ Pr[𝐷1 accepts] − Pr[𝑧 is bad] ≥ .
e
𝑧 4
The rest of a proof of the correctness is essentially the same with the case of 𝐷0 , observing that
the security proof of the Nisan–Wigderson generator also works for the modified version NW0.
Finally, we convert the randomized read-once branching program 𝐷1 of size 𝑁 𝛽 into a
co-nondeterministic read-once branching program of size 𝑁 1+𝛽 . This can be done by using the
standard Adleman’s trick [1]: Specifically, the success probability of 𝐷1 can be amplified to
1 − 2−𝑁 by taking AND of 𝑂(𝑁) independent copies of 𝐷1 . By the union bound, there exists
a good coin flip sequence such that AND of 𝑂(𝑁) copies of 𝐷1 solves (ΠYes , ΠNo ) on every
input of length 𝑁. Hard-wiring such a coin flip sequence and simulating the AND gate by
using a co-nondeterministic computation, we obtain a co-nondeterministic read-once branching
program of size 𝑂(𝑁 1+𝛽 ).
5 Non-trivial derandomization and MKtP
In this section, we provide a characterization of non-trivial derandomization for uniform
algorithms by a lower bound for MKtP. We start with a formal definition of non-trivial
derandomization for uniform algorithms.
Definition 5.1 (Non-trivial derandomization). An algorithm 𝐴 is said to be a derandomization
algorithm for DTIME(𝑡(𝑛)) that runs in time 𝑠(𝑛) if the following hold. The algorithm takes 1𝑛 and
a description of a machine 𝑀 and outputs an 𝑛-bit string 𝐴(1𝑛 , 𝑀) ∈ {0, 1} 𝑛 in time 𝑠(𝑛). For
any machine 𝑀 running in time 𝑡(𝑛) on inputs of length 𝑛 ∈ ℕ , there exist infinitely many 𝑛 ∈ ℕ
such that, if Pr𝑥∼{0,1}𝑛 [𝑀(𝑥) = 1] ≥ 12 , then 𝑀(𝐴(1𝑛 , 𝑀)) = 1.
𝑠
In the following, for a function 𝑠 : ℕ → ℕ , we denote by 𝑅 Kt the set { 𝑥 ∈ {0, 1}∗ | Kt(𝑥) ≥
𝑠(|𝑥|) } of Kt-random strings with threshold 𝑠. We say that a set 𝑅 ⊆ {0, 1}∗ is dense if
Pr𝑥∼{0,1}𝑛 [𝑥 ∈ 𝑅] ≥ 12 for all large 𝑛 ∈ ℕ .
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 47
S HUICHI H IRAHARA
Proposition 5.2. The following are equivalent for any time-constructible functions 𝑡(𝑛) ≥ 𝑛 and 𝑠(𝑛).
1. There exists a derandomization algorithm for DTIME(𝑡(𝑛)) that runs in time 2𝑠(𝑛)+𝑂(log 𝑡(𝑛)) .
𝑠(𝑛)+𝑂(log 𝑡(𝑛))
2. Any dense subset of 𝑅 Kt cannot be accepted by any 𝑡(𝑛)-time algorithm.
Proof. (Item 1 =⇒ Item 2) Let 𝐴 be a derandomization algorithm for DTIME(𝑡(𝑛)). Since
𝐴 runs in time 2𝑠(𝑛)+𝑂(log 𝑡(𝑛)) on input (1𝑛 , 𝑀), the Kt-complexity of 𝐴(1𝑛 , 𝑀) is at most
𝑠(𝑛) + 𝑂(log 𝑡(𝑛)) + |𝑀|.
Let 𝑀 be any 𝑡(𝑛)-time algorithm such that Pr𝑥∼{0,1}𝑛 [𝑀(𝑥) = 1] ≥ 12 for all large 𝑛 ∈ ℕ . By
the property of 𝐴, we have 𝑀(𝐴(1𝑛 , 𝑀)) = 1 for infinitely many 𝑛. This means that 𝑀 accepts
the string 𝐴(1𝑛 , 𝑀) that has Kt-complexity at most 𝑠(𝑛) + 𝑂(log 𝑡(𝑛)); therefore, 𝑀 does not
accept a dense subset of Kt-random strings.
(Item 2 =⇒ Item 1) Let 𝐴 be the algorithm that takes (1𝑛 , 𝑀), enumerates all the strings 𝑥
whose Kt-complexity is at most 𝑠(𝑛)+𝑂(log 𝑡(𝑛)), and, for each string 𝑥 with small Kt-complexity,
simulates 𝑀 on input 𝑥; if 𝑀 accepts 𝑥 in time 𝑡(𝑛), output 𝑥 and halt. The running time of
𝐴 is clearly at most 2𝑠(𝑛)+𝑂(log 𝑡(𝑛)) . To prove the correctness, assume towards a contradiction
that some algorithm 𝑀 runs in time 𝑡(𝑛) and for all large 𝑛, Pr𝑥∼{0,1}𝑛 [𝑀(𝑥) = 1] ≥ 12 and
𝑀(𝐴(1𝑛 , 𝑀)) = 0. The latter condition means that 𝐴 cannot find a string 𝑥 that is accepted by
𝑀; thus, 𝑀 rejects all the strings 𝑥 whose Kt-complexity is at most 𝑠(𝑛) + 𝑂(log 𝑡(𝑛)). Therefore,
𝑀 accepts a dense subset of Kt-random strings, which is a contradiction.
Theorem 5.3. Let 𝑡, 𝑠 : ℕ → ℕ be time-constructible functions such that 𝑡 is non-decreasing and
𝜔(log2 𝑛) ≤ 𝑠(𝑛) ≤ 𝑛 and poly(𝑛) ≤ 𝑡(2𝑠(𝑛)) for all large 𝑛, where poly is some universal polynomial.
For any constant 𝑐 > 0, there exists
√
a constant 𝑐 0 such that, if there is a 𝑡(𝑛)-time algorithm
𝑛−𝑐 𝑛 log 𝑛
that accepts a dense subset of 𝑅 Kt , then the following promise problem can be solved in
√
DTIME(𝑂(𝑡(2𝑠(𝑛)) · 2 𝑠(𝑛) log 𝑛 )) ∩ coRTIME(𝑂(𝑡(2𝑠(𝑛)))).
Yes: strings 𝑥 such that Kt(𝑥) ≤ 𝑠, where 𝑠 := 𝑠(|𝑥|).
√
No: strings 𝑥 such that K𝑡 (𝑥) > 𝑠 + 𝑐 0 𝑠 log 𝑛, where 𝑠 := 𝑠(|𝑥|) and 𝑡 0 = 𝑡(2𝑠) · poly(|𝑥|).
0
Lemma 5.4 (see [32]). For any 𝑑, 𝑚 ≤ 𝑛, 𝜖 > 0, there exists a black-box pseudorandom generator
construction 𝐺 𝑥 : {0, 1} 𝑑 → {0, 1} 𝑚 that takes a string 𝑥 ∈ {0, 1} 𝑛 and satisfies the following.
1. For any 𝜖-distinguisher 𝑇 : {0, 1} 𝑚 → {0, 1} for 𝐺 𝑥 , it holds that
K𝑡,𝑇 (𝑥) ≤ exp(ℓ 2 /𝑑) · 𝑚 + 𝑑 + 𝑂(log(𝑛/𝜖)),
where ℓ = 𝑂(log 𝑛) and 𝑡 = poly(𝑛, 1/𝜖).
2. 𝐺 𝑥 (𝑧) is computable in time poly(𝑛, 1/𝜖).
Proof Sketch. The pseudorandom generator construction 𝐺 𝑥 is defined as 𝐺 𝑥 (𝑧) := NWEnc(𝑥) (𝑧)
for any 𝑧 ∈ {0, 1} 𝑑 , where NW is the Nisan–Wigderson generator [56] that is instantiated
with the weak design of [61] and the function whose truth table is Enc(𝑥) as a candidate hard
function.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 48
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
Proof of Theorem 5.3. Fix 𝑛 ∈ ℕ and an input 𝑥 ∈ {0, 1} 𝑛 . For simplicity, let 𝑠 := 𝑠(𝑛). Define 𝑑 :=
√
𝑠 log 𝑛. Since 𝑠(𝑛) = 𝜔(log2 𝑛), we have 4𝑐𝑑 ≤ 𝑠 for a sufficiently large
√
𝑛. Set 𝑚 := 𝑠 + 4𝑐𝑑 ≤ 2𝑠.
𝑛−𝑐 𝑛 log 𝑛
Let 𝐷 be the 𝑡(𝑛)-time algorithm that accepts a dense subset of 𝑅 Kt .
We claim that there exists a coRP-type algorithm 𝐴 that uses 𝑑 random bits and solves the
promise problem. The algorithm 𝐴 operates as follows. Pick a random seed 𝑧 ∈ {0, 1} 𝑑 , and
accept if and only if 𝐷(𝐺 𝑥 (𝑧)) = 0, where the output length of 𝐺 𝑥 is set to be 𝑚. This runs in
time 𝑡(𝑚) + poly(𝑛) ≤ 𝑂(𝑡(2𝑠)) and can be derandomized in time 𝑂(𝑡(2𝑠)) · 2𝑑 by exhaustively
trying all the random bits.
It remains to prove the correctness of the algorithm 𝐴. Assume that Kt(𝑥) ≤ 𝑠. Then, since
𝐺 𝑥 (𝑧) is computable in polynomial time, for any 𝑧 ∈ {0, 1} 𝑑 , we have
√
Kt(𝐺 𝑥 (𝑧)) ≤ 𝑑 + 𝑠 + 𝑂(log 𝑛) ≤ 𝑠 + 2𝑑 ≤ 𝑠 + 4𝑐𝑑 − 2𝑐𝑑 < 𝑚 − 𝑐 𝑚 log 𝑛,
√ √
where, in the√ last inequality, we used the fact that 𝑚 log 𝑛 ≤ 2𝑠 log 𝑛 < 2𝑑. Therefore,
𝑚−𝑐 𝑚 log 𝑚
𝐺 𝑥 (𝑧) ∉ 𝑅Kt , which is rejected by 𝐷; hence, 𝐴 accepts.
Conversely, assume that the probability that 𝐴 accepts is at least 34 . This means that
3
Pr [𝐷(𝐺 𝑥 (𝑧)) = 0] ≥ .
𝑧∼{0,1} 𝑑 4
Since we have
1
Pr [𝐷(𝑤) = 0] ≤ ,
𝑤∼{0,1} 𝑚 2
𝐷 is a distinguisher for 𝐺 𝑥 . By the security of Lemma 5.4, we obtain that, for 𝑡 0 := poly(𝑛) · 𝑡(𝑚),
K𝑡 (𝑥) ≤ exp(ℓ 2 /𝑑) · 𝑚 + 𝑂(log 𝑛)
0
≤ (1 + 2ℓ 2 /𝑑) · (𝑠 + 4𝑐𝑑) + 𝑂(log 𝑛)
√
≤ 𝑠 + 𝑂( 𝑠 log 𝑛),
√
which can be bounded above by 𝑠 + 𝑐 0 𝑠 log 𝑛 by choosing a large enough constant 𝑐 0. Thus, 𝑥
is not a No instance of the promise problem. Taking the contrapositive, we conclude that any
No instance 𝑥 is rejected by 𝐴 with probability at least 14 .
In the special case when 𝑡(𝑛) = 𝑛 𝑂(1) , Theorem 5.3 implies that the Kt vs K𝑡 Problem can be
solved in coRP.
√
Proof Sketch of Theorem 1.15. We claim that the Kt vs K𝑡 Problem can be solved in time 2𝑂( 𝑛)
e
under the assumption that MKtP ∈ P. We use the same proof of Theorem 5.3 for 𝑡(𝑛) := 𝑛 log 𝑛
when the parameter 𝑠 = 𝜔(log2 𝑛); when 𝑠 = 𝑂(log2 𝑛), we set 𝑑 := ℓ 2 and 𝑚 := 𝑂(𝑑) as in
[32].
Theorem 5.5 (A formal version of Theorem 1.14). For any constant 0 < 𝜖 < 1, the following are
equivalent.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 49
S HUICHI H IRAHARA
√
1. For some 𝑐1 , for any
√
large 𝑐2 , there exists no derandomization algorithm for DTIME(2𝑐1 𝑛 log 𝑛 ) that
𝑛−𝑐
runs in time 2 2 log 𝑛 .
𝑛
√
2. For some 𝑐1 , for any large
√
𝑐2 , there exists an algorithm running in time 2𝑐1 𝑛 log 𝑛 that accepts a
𝑛−𝑐 𝑛 log 𝑛
dense subset of 𝑅 Kt 2 .
√ √
3. For some 𝑐 1 , for any large 𝑐 2 , MKtP[𝑛 − 𝑐2 𝑛 log 𝑛, 𝑛 − 1] ∈ DTIME(2𝑐1 𝑛 log 𝑛 ).
√ √
𝜖
4. For some 𝑐 1 , for any large 𝑐 2 , MKtP[𝑛 𝜖 , 𝑛 𝜖 + 𝑐 2 𝑛 𝜖 log 𝑛] ∈ DTIME(2𝑐1 𝑛 log 𝑛 ).
Proof. (Item 1 ⇐⇒ Item 2) This equivalence follows from Proposition√
5.2.
(Item 2 =⇒ Item 4) We√apply Theorem 5.3 for 𝑡(𝑛) := 2 𝑐 1 𝑛 log 𝑛 and 𝑠(𝑛) := 𝑛 𝜖 . Then we
obtain a DTIME(𝑂(𝑡(2𝑠)) · 2 𝑠 log 𝑛 )-algorithm 𝐴 that distinguishes Yes instances 𝑥 such that
𝑡 0 √
Kt(𝑥) ≤ 𝑠 from No instances 𝑥 such that K (𝑥) > 𝑠 + 𝑐 2 𝑠 log 𝑛, where 𝑡 0 = 𝑡(2𝑠) · poly(𝑛) and 𝑐 20
0
√ √
is some constant. We choose a constant 𝑐10 large enough so that 𝑂(𝑡(2𝑠)) · 2 𝑠 log 𝑛 ≤ 2𝑐1 𝑠 log 𝑛 ,
0
which bounds from above the running time of the algorithm 𝐴.
√
We claim that MKtP[𝑠, 𝑠 +𝑐 200 𝑠 log 𝑛] is also solved by 𝐴 for any sufficiently large 𝑐200. Take any
√ √
string 𝑥 such that Kt(𝑥) ≥ 𝑠 +𝑐200 𝑠 log 𝑛. Since Kt(𝑥) ≤ K𝑡 (𝑥)+𝑂(log 𝑡 0) ≤ K𝑡 (𝑥)+𝑂(𝑐1 𝑠 log 𝑛),
0 0
√ √ √
it follows that K𝑡 (𝑥) ≥ 𝑠 + 𝑐 200 𝑠 log 𝑛 − 𝑂(𝑐 1 𝑠 log 𝑛) > 𝑠 + 𝑐 20 𝑠 log 𝑛, where the last inequality
0
holds for any sufficiently large 𝑐 200; thus, 𝑥 is rejected by 𝐴.
(Item 4 =⇒ Item 3) By the assumption, there exists a constant 𝑐 1 such that,√for all large 𝑐2 ,
√ 𝑐 1 𝑛 𝜖 log 𝑛 . Define
there exists an algorithm 𝐴 that solves MKtP[𝑛 𝜖 , 𝑛 𝜖 + 𝑐2 𝑛 𝜖 log 𝑛] in time 2√
𝑐 10 := 𝑐1 /𝜖. For all large 𝑐20 , we construct an algorithm 𝐵 that solves MKtP[𝑛 − 𝑐 20 𝑛 log 𝑛, 𝑛 − 1] in
√
time 2𝑐1 𝑛 log 𝑛 . The algorithm 𝐵 takes an input 𝑥 of length 𝑛 and√simulates 𝐴 on√input 𝑥10𝑚−𝑛−1
0
for
√ 𝑐 𝑚 𝑚 𝑐 𝑚 𝑛 𝑐
√
0 𝑚 log 𝑛
𝑚 := (𝑛 − 2𝑐2 𝑛 log 𝑛) . The running time of 𝐵 is at most 2 1
1/𝜖 log ≤21 /𝜖· log =21 .
𝑛
√
It remains to prove the correctness of 𝐵. Take any 𝑥 ∈ {0, 1} such that Kt(𝑥) ≤ 𝑛 − 𝑐 2 𝑛 log 𝑛.
0
√
Then we have Kt(𝑥10𝑚−𝑛−1 ) ≤ 𝑛 − 𝑐20 𝑛 log 𝑛 + 𝑂(log 𝑛) ≤ 𝑚 𝜖 for any large 𝑐2 ; thus 𝐵 accepts 𝑥.
Conversely, take any 𝑥 such that Kt(𝑥)√≥ 𝑛 − 1. Then we have Kt(𝑥10𝑚−𝑛−1 ) ≥ 𝑛 − 𝑂(log 𝑛) =
√
𝑚 𝜖 + 2𝑐2 𝑛 log 𝑛 − 𝑂(log 𝑛) ≥ 𝑚 𝜖 + 𝑐2 𝑚 𝜖 log 𝑛; thus, 𝐵 rejects.
(Item 3 =⇒ Item 2) This immediately follows√from the fact that the complement of
√ 𝑛−𝑐 𝑛 log 𝑛+1
MKtP[𝑛 − 𝑐2 𝑛 log 𝑛, 𝑛 − 1] is a dense subset of 𝑅Kt 2 .
A Derandomized hardness amplification theorem
We review a simplified proof of derandomized hardness amplification given by Healy, Vadhan
and Viola [31], and observe that the parameter shown in Theorem 4.24 can be achieved by
slightly modifying the construction.
Theorem 4.24 (Derandomized hardness amplification). Let 𝛾 > 0 be an arbitrary constant. There
exists a hardness amplification procedure Amp that takes a function 𝑓 : {0, 1} 𝑛 → {0, 1} and parameters
𝑓
𝛿, 𝜖 > 0, and returns a Boolean function Amp𝜖,𝛿 : {0, 1} 𝑂(𝑛+log(1/𝜖)) → {0, 1} satisfying the following:
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 50
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
𝑓
1. If size(Amp
g
𝜖,𝛿
; 1/2 − 𝜖) ≤ 𝑠, then size(
g 𝑓 ; 𝛿) ≤ 𝑠 · poly(1/𝜖, 1/𝛿).
2. For any fixed 𝑦 ∈ {0, 1} 𝑂(𝑛+log(1/𝜖)) , there exist strings 𝑣 1 , · · · , 𝑣 𝑘 ∈ {0, 1} 𝑛 for some 𝑘 =
𝑓
𝑂(log(1/𝜖)/𝛿) such that Amp𝜖,𝛿 (𝑦) = 𝑓 (𝑣 1 ) ⊕ · · · ⊕ 𝑓 (𝑣 𝑘 ). Moreover, if 𝑦 is distributed
uniformly at random, for each 𝑖 ∈ [𝑘], 𝑣 𝑖 is distributed uniformly at random.
𝑓
3. Amp𝜖,𝛿 (𝑦) can be computed in 𝑂(𝑛 + log(1/𝛿) + log(1/𝜖)) space, given 𝑓 , 𝑦, 𝜖 and 𝛿 as an input.
First, we explain the construction of our hardness amplification procedure. The construction
is a XOR of the nearly disjoint generator ND and a hitter Hit (see [25]). In fact, we need a slightly
generalized version of a hitter, for which we show that the same construction of [25] suffices.
We note that in the previous works [44, 31], an expander walk was used instead of Hit; this does
not give us a nearly optimal construction of a hitter when 𝛿 is not a constant.
Lemma A.1. There exists a “hitter” Hit such that, given parameters 𝑛 ∈ ℕ , 𝜖, 𝛿 > 0, a function
Hit𝑛,𝜖,𝛿 : {0, 1} 𝑂(𝑛+log(1/𝜖)) → ({0, 1} 𝑛 ) 𝑘 𝑛,𝜖,𝛿 takes a seed of length 𝑂(𝑛 + log(1/𝜖)) and outputs a list
𝐿 of 𝑘 𝑛,𝜖,𝛿 = 𝑂(log(1/𝜖)/𝛿) strings of length 𝑛 such that, for any subsets 𝐻1 , · · · , 𝐻 𝑘 𝑛,𝜖,𝛿 ⊆ {0, 1} 𝑛 of
size ≥ 𝛿2𝑛 , with probability at least 1 − 𝜖, there exists an index 𝑖 ∈ [𝑘 𝑛,𝜖,𝛿 ] such that the 𝑖th string in the
list 𝐿 is in 𝐻𝑖 . Moreover, KS(𝐿) ≤ 𝑂(𝑛 + log(1/𝜖)).
Proof Sketch. We observe that the construction of [25, Appendix C] satisfies the requirement of
Lemma A.1. The construction is as follows: First, we take a pairwise independent generator
𝐺2 : {0, 1} 𝑂(𝑛) → ({0, 1} 𝑛 )𝑂(1/𝛿) . By Chebyshev’s inequality, with probability at least 12 over the
choice of a seed 𝑟 ∈ {0, 1} 𝑂(𝑛) , 𝐺2 hits some 𝐻𝑖 , · · · , 𝐻𝑖+𝑂(1/𝛿) , where 𝑖 is an arbitrary index. Now
we take an explicit construction of a constant-degree expander on 2𝑂(𝑛) vertices, and generate a
random walk 𝑣 1 , · · · , 𝑣ℓ of length ℓ = 𝑂(log(1/𝜖)) over {0, 1} 𝑂(𝑛) , which takes random bits of
length 𝑂(𝑛 + log(1/𝜖)). The output of Hit is defined as the concatenation of 𝐺2 (𝑣 1 ), · · · , 𝐺2 (𝑣ℓ ).
The correctness follows by using the Expander Random Walk Theorem [25, Theorem A.4].
Definition A.2. Let 𝑓 be a function 𝑓 : {0, 1} 𝑛 → {0, 1}, and 𝜖, 𝛿 > 0 be arbitrary parameters.
Let 𝑘 := 𝑘 𝑛,𝜖,𝛿 . Let ND : {0, 1} 𝑂(𝑛) → ({0, 1} 𝑛 ) 𝑘 be the nearly disjoint generator (Definition 4.17)
defined with the design of Lemma 4.16. We define a generator
IW𝑛,𝜖,𝛿 : {0, 1} 𝑂(𝑛+log(1/𝜖)) → ({0, 1} 𝑛 ) 𝑘
as
IW𝑛,𝜖,𝛿 (𝑥, 𝑦) := ND(𝑥) ⊕ Hit(𝑦).
Then we define a hardness amplified version
𝑓
Amp𝜖,𝛿 : {0, 1} 𝑂(𝑛+log(1/𝜖)) → {0, 1}
𝑓
of 𝑓 as the function Amp𝜖,𝛿 := 𝑓 ⊕𝑘 ◦ IW𝑛,𝜖,𝛿 .
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 51
S HUICHI H IRAHARA
We proceed to a proof of Theorem 4.24. We recall several notions from [31]. For a subset
𝐻 ⊆ {0, 1} 𝑛 (which is supposed to be a hard-core set) and a function 𝑓 : {0, 1} 𝑛 → {0, 1}, we
consider a probabilistic function 𝑓𝐻 : {0, 1} 𝑛 → {0, 1}, i. e., a distribution over Boolean functions,
defined as follows: For each 𝑥 ∈ 𝐻, the value 𝑓𝐻 (𝑥) is defined as a random bit chosen uniformly
at random and independently; For each 𝑥 ∈ {0, 1} 𝑛 \ 𝐻, the value 𝑓𝐻 (𝑥) is defined as 𝑓 (𝑥).
Assuming that 𝐻 is indeed a hard-core set for 𝑓 , the distributions (𝑥, 𝑓 (𝑥)) and (𝑥, 𝑓𝐻 (𝑥)) where
𝑥 ∼ {0, 1} 𝑛 are computationally indistinguishable. Indeed:
Proposition A.3 (see [70]). Let 𝐻 ⊆ {0, 1} 𝑛 be an arbitrary subset, 𝑓 : {0, 1} 𝑛 → {0, 1} be an arbitrary
function, and 𝜖 > 0 be an arbitrary parameter. If
Pr [𝐴(𝑥, 𝑓 (𝑥)) = 1] − Pr [𝐴(𝑥, 𝑓𝐻 (𝑥)) = 1] ≥ 𝜖,
𝑥∼{0,1} 𝑛 𝑥∼{0,1} 𝑛
for some function 𝐴 : {0, 1} 𝑛+1 → {0, 1}, then there exists a one-query oracle circuit of size 𝑂(1) such
that
1 𝜖
Pr [𝐶 𝐴 (𝑥) = 𝑓 (𝑥)] ≥ + .
𝑥∼𝐻 2 𝛿
For a probabilistic function ℎ : {0, 1} 𝑛 → {0, 1}, the expected bias of ℎ is defined as
ExpBias[ℎ] := 𝔼𝑥∼{0,1}𝑛 [Bias(ℎ(𝑥))], where the bias Bias(𝑏) of a binary random variable 𝑏 ∈ {0, 1}
is defined as
Bias(𝑏) = Pr[𝑏 = 0] − Pr[𝑏 = 1] .
𝑏 𝑏
It was shown in [31] that the hardness of 𝑓 ⊕𝑘 ◦ 𝐺(𝑧) is essentially characterized by the
expected bias of ExpBias[ 𝑓𝐻⊕𝑘 ◦ IW], using a property of the nearly disjoint generator ND.
Lemma A.4 ([31, Lemma 5.2 and Lemma 5.12]). Let 𝑔 be an arbitrary probabilistic function, and
𝜖 > 0 be arbitrary parameters. Suppose that there exists a function 𝐴 such that
1 1 𝜖
Pr[𝐴(𝑧) = 𝑓 ⊕𝑘 ◦ IW(𝑧)] ≥ + ExpBias[𝑔 ⊕𝑘 ◦ IW] +
𝑧 2 2 2
Then there exists a one-query oracle circuit 𝐶 of size 𝑂(𝑘 · 2𝛾𝑛 ) such that
𝜖
𝔼[𝐶 𝐴 (𝑥, 𝑓 (𝑥)) − 𝐶 𝐴 (𝑥, 𝑔(𝑥))] ≥ ,
𝑥 2𝑘
where 𝛾 > 0 is an arbitrary constant of Lemma 4.16.
We will apply Lemma A.4 for 𝑔 := 𝑓𝐻 . By using a property of the hitter, we show that the
expected bias of 𝑓𝐻 is small whenever a hard-core set 𝐻 is large enough.
Lemma A.5. Let 𝜖, 𝛿 > 0 be arbitrary parameters, and 𝐻 ⊆ {0, 1} 𝑛 be a subset of size at least 𝛿2𝑛 . Let
𝑘 := 𝑘 𝑛,𝜖,𝛿 . Then ExpBias[ 𝑓𝐻⊕𝑘 ◦ IW𝑛,𝜖,𝛿 ] ≤ 𝜖
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 52
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
Proof. The idea is that when a hitter hits a hard-core set 𝐻, the expected bias becomes 0. More
specifically, recall that IW(𝑥, 𝑦) is defined as ND(𝑥) ⊕ Hit𝑛,𝜖,𝛿 (𝑦). Fix any 𝑥, and define 𝐻𝑖 as a
shifted version of 𝐻: namely, 𝐻𝑖 := ND(𝑥)𝑖 ⊕ 𝐻 := { ND(𝑥)𝑖 ⊕ ℎ | ℎ ∈ 𝐻 } for every 𝑖 ∈ [𝑘]. We
apply Lemma A.1 for 𝐻1 , · · · , 𝐻 𝑘 . Since |𝐻𝑖 | = |𝐻 | ≥ 𝛿2𝑛 for every 𝑖 ∈ [𝑘], by the property of the
hitter, there exists some index 𝑖 ∈ [𝑘] such that Hit𝑛,𝜖,𝛿 (𝑦)𝑖 ∈ 𝐻𝑖 = ND(𝑥)𝑖 ⊕ 𝐻 with probability
at least 1 − 𝜖 over the choice of 𝑦. In this case, IW𝑛,𝜖,𝛿 (𝑥, 𝑦)𝑖 = ND(𝑥)𝑖 ⊕ Hit𝑛,𝜖,𝛿 (𝑦)𝑖 ∈ 𝐻, and
hence the bias of 𝑓𝐻 (IW𝑛,𝜖,𝛿 (𝑥, 𝑦)) is exactly 0. Therefore,
ExpBias[ 𝑓𝐻⊕𝑘 ◦ IW𝑛,𝜖,𝛿 ]
≤ Pr Bias( 𝑓𝐻⊕𝑘 ◦ IW𝑛,𝜖,𝛿 (𝑥, 𝑦)) > 0
𝑥,𝑦
≤ Pr IW𝑛,𝜖,𝛿 (𝑥, 𝑦)𝑖 ∉ 𝐻 for every 𝑖 ∈ [𝑘] ≤ 𝜖
𝑥,𝑦
Now we combine Proposition A.3 and Lemmas A.4 and A.5 and obtain the following:
Corollary A.6. Let 𝑛 ∈ ℕ and 𝜖, 𝛿 > 0. Let 𝐻 ⊆ {0, 1} 𝑛 be an arbitrary subset of size at least 𝛿2𝑛 . If
some function 𝐴 satisfies
1
Pr[𝐴(𝑧) = 𝑓 ⊕𝑘 ◦ IW𝑛,𝜖,𝛿 (𝑧)] ≥ +𝜖
𝑧 2
then there exists a one-query oracle circuit 𝐶 of size 𝑂(𝑘 · 2𝛾𝑛 ) such that,
1 𝜖
Pr [𝐶 𝐴 (𝑥) = 𝑓 (𝑥)] ≥ + .
𝑥∼𝐻 2 2𝛿𝑘
At this point, we make use of Impagliazzo’s hard-core lemma [42]. Equivalently, one can
view it as a boosting algorithm (see [47]).
Lemma A.7 (see [42, 47]). Under the condition of Corollary A.6, there exists an oracle circuit 𝐶 of size
𝑂(𝑘 · 2𝛾𝑛 ) · poly(𝑘/𝜖) such that
Pr [𝐶 𝐴 (𝑥) = 𝑓 (𝑥)] ≥ 1 − 𝛿.
𝑥∼{0,1} 𝑛
Now we take any circuit 𝐴 of size 𝑠 such that
𝑓 1
Pr[𝐴(𝑧) = Amp𝜖,𝛿 (𝑧)] ≥ + 𝜖.
𝑧 2
By using Corollary A.6 and Lemma A.7 and replacing each oracle gate by a circuit 𝐴, we obtain
a circuit 𝐶 of size 𝑂(𝑘 · 2𝛾𝑛 ) · poly(𝑘/𝜖) · 𝑠 such that
Pr [𝐶(𝑥) = 𝑓 (𝑥)] ≥ 1 − 𝛿.
𝑥∼{0,1} 𝑛
This completes the proof of Theorem 4.24.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 53
S HUICHI H IRAHARA
B AC0 Lower Bounds for MKtP
In this section, we prove that there exists no constant-depth fixed-polynomial-size circuit that
computes MKtP[𝑂(log 𝑁), 𝑁 𝑜(1) ].
Proposition B.1. For any constants 𝛼 < 1, 𝑘, 𝑑 ∈ ℕ , there exists a constant 𝑐 such that
MKtP[𝑐 log 𝑁 , 𝑁 𝛼 ] ∉ i.o.AC0𝑑 (𝑁 𝑘 ).
Previously, [14] used the pseudorandom restriction of Trevisan and Xue [72] to obtain
0
AC lower bounds for MKtP[polylog𝑁]. Here we make use of a polynomial-time-computable
pseudorandom restriction that shrinks AC0 circuits, which enables us to prove a lower bound for
MKtP[𝑂(log 𝑁)]. The following lemma is proved in the context of quantified derandomization.
Lemma B.2 (Goldreich and Wigderson [27]). For any constants 𝛼 < 1 and 𝑑 ∈ ℕ and any polynomials
𝑝, 𝑞, there exists a constant 𝑘 and a polynomial-time algorithm of 𝑂(log 𝑛) randomness complexity that
produces restrictions on 𝑛 variables such that the following conditions hold:
1. The number of undetermined variables in each restriction is at least 2𝑛 𝛼 .
2. For any 𝑛-input circuit of depth 𝑑 and size at most 𝑝(𝑛), with probability at least 1 − 1/𝑞(𝑛), the
corresponding restricted circuit depends on at most 𝑘 variables.
Proof of Proposition B.1. Fix any polynomial 𝑝 and a depth 𝑑. We claim that, for some constant
𝑐 > 0, there exists no depth-𝑑 circuit of size 𝑝(𝑛) that computes MKtP[𝑐 log 𝑛, 𝑛 𝛼 ] for all large 𝑛.
Assume, towards a contradiction, that there exists a depth-𝑑 circuit 𝐶 of size 𝑝(𝑛) that computes
MKtP[𝑐 log 𝑛, 𝑛 𝛼 ]. We use Lemma B.2 for 𝑞 ≡ 2. Then, there exists a polynomial-time algorithm
that produces a pseudorandom restriction 𝜌 that shrinks 𝐶 to a circuit of size 𝑘 = 𝑂(1) with
probability at least 12 . Fix one pseudorandom restriction 𝜌 such that the restricted circuit 𝐶 𝜌 is
a constant-size circuit.
We claim that 𝐶 does not compute MKtP[𝑐 log 𝑛, 𝑛 𝛼 ]. Let 𝜎 be the restriction that fixes 𝑘
variables on which 𝐶 𝜌 depend to 0. Consider 0𝑛 ◦ 𝜌 = 0𝑛 ◦ 𝜎 ◦ 𝜌, i. e., the string obtained by
fixing undetermined variables in 𝜌 to 0. Since 𝜌 is generated by a polynomial-time algorithm,
there exists a constant 𝑐 such that Kt(0𝑛 ◦ 𝜌) ≤ 𝑐 log 𝑛. Thus, 0𝑛 ◦ 𝜎 ◦ 𝜌 is a Yes instance of
MKtP[𝑐 log 𝑛, 𝑛 𝛼 ]. Since 𝐶 𝜎◦𝜌 is a constant circuit, we have 1 = 𝐶 𝜎◦𝜌 (0𝑛 ) = 𝐶 𝜎◦𝜌 (𝑥) for
any 𝑥 ∈ {0, 1} 𝑛 . However, for a random 𝑥 ∈ {0, 1} 𝑛 , by a simple counting argument, it holds
that Kt(𝑥 ◦ 𝜎 ◦ 𝜌) ≥ 2𝑛 𝛼 − 𝑘 − 1 > 𝑛 𝛼 with high probability. Therefore, 𝑥 ◦ 𝜎 ◦ 𝜌 is a No instance
of MKtP[𝑐 log 𝑛, 𝑛 𝛼 ] for some 𝑥, which is a contradiction.
References
[1] Leonard M. Adleman: Two theorems on random polynomial time. In Proc. 19th FOCS, pp.
75–83. IEEE Comp. Soc., 1978. [doi:10.1109/SFCS.1978.37] 19, 37, 47
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 54
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
[2] Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef
Ronneburger: Power from random strings. SIAM J. Comput., 35(6):1467–1493, 2006.
[doi:10.1137/050628994] 14, 15, 17, 30, 32
[3] Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, and Michael E. Saks:
Minimizing disjunctive normal form formulas and AC0 circuits given a truth table. SIAM J.
Comput., 38(1):63–84, 2008. [doi:10.1137/060664537] 10, 15
[4] Eric Allender and Shuichi Hirahara: New insights on the (non-)hardness of circuit
minimization and related problems. ACM Trans. Comput. Theory, 11(4):27:1–27, 2019.
[doi:10.1145/3349616] 15, 30
[5] Eric Allender and Michal Koucký: Amplifying lower bounds by means of self-reducibility.
J. ACM, 57(3):14:1–36, 2010. [doi:10.1145/1706591.1706594] 16
[6] László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson: BPP has subexponential
time simulations unless EXPTIME has publishable proofs. Comput. Complexity, 3(4):307–318,
1993. [doi:10.1007/BF01275486] 3
[7] Manuel Blum and Silvio Micali: How to generate cryptographically strong sequences of
pseudo-random bits. SIAM J. Comput., 13(4):850–864, 1984. [doi:10.1137/0213053] 3
[8] Andrej Bogdanov and Luca Trevisan: On worst-case to average-case reductions for NP
problems. SIAM J. Comput., 36(4):1119–1159, 2006. [doi:10.1137/S0097539705446974] 4, 18
[9] Allan Borodin, Alexander A. Razborov, and Roman Smolensky: On lower bounds for read-
𝑘-times branching programs. Comput. Complexity, 3(1):1–18, 1993. [doi:10.1007/BF01200404]
13, 16
[10] Harry Buhrman, Lance Fortnow, and Aduri Pavan: Some results on derandomization.
Theory Computing Sys., 38(2):211–227, 2005. [doi:10.1007/s00224-004-1194-y] 5, 7, 24, 25
[11] Harry Buhrman, Lance Fortnow, and Rahul Santhanam: Unconditional lower bounds
against advice. In Proc. 36th Internat. Colloq. on Automata, Languages, and Programming
(ICALP’09), pp. 195–209. Springer, 2009. [doi:10.1007/978-3-642-02927-1_18] 7
[12] Harry Buhrman and Steven Homer: Superpolynomial circuits, almost sparse oracles
and the exponential hierarchy. In Proc. 12th Found. Softw. Techn. Theoret. Comp. Sci. Conf.
(FSTTCS’92), pp. 116–127. Springer, 1992. [doi:10.1007/3-540-56287-7_99] 28
[13] Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina
Kolokolova: Learning algorithms from Natural Proofs. In Proc. 31st Comput. Complexity
Conf. (CCC’16), pp. 10:1–24. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016.
[doi:10.4230/LIPIcs.CCC.2016.10] 15
[14] Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, and
Rahul Santhanam: Beyond Natural Proofs: Hardness magnification and locality. J. ACM,
69(4):25:1–49, 2022. Preliminary version in ITCS’20. [doi:10.1145/3538391] 11, 16, 54
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 55
S HUICHI H IRAHARA
[15] Lijie Chen, Ce Jin, and R. Ryan Williams: Hardness magnification for all sparse
NP languages. In Proc. 60th FOCS, pp. 1240–1255. IEEE Comp. Soc., 2019.
[doi:10.1109/FOCS.2019.00077] 16
[16] Kuan Cheng and William M. Hoza: Hitting sets give two-sided derandomization of
small space. Theory of Computing, 18(21):1–32, 2022. Preliminary version in CCC’20.
[doi:10.4086/toc.2022.v018a021] 13
[17] Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, and Yuichi Yoshida: One-tape
Turing machine and branching program lower bounds for MCSP. Theory Computing Sys.,
(10113-9):32 pages, 2022. Preliminary version in MFCS’21. [doi:10.1007/s00224-022-10113-9]
13
[18] Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, and Dimitrios Myrisiotis: Circuit
lower bounds for MCSP from local pseudorandom generators. ACM Trans. Comput. Theory,
12(3):21:1–27, 2020. Preliminary version in ICALP’19. [doi:10.1145/3404860] 11
[19] Shimon Even, Alan L. Selman, and Yacov Yacobi: The complexity of promise prob-
lems with applications to public-key cryptography. Inform. Control, 61(2):159–173, 1984.
[doi:10.1016/S0019-9958(84)80056-X] 2
[20] Joan Feigenbaum and Lance Fortnow: Random-self-reducibility of complete sets. SIAM J.
Comput., 22(5):994–1005, 1993. [doi:10.1137/0222061] 4
[21] Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, and Alexander S.
Kulikov: A better-than-3𝑛 lower bound for the circuit complexity of an explicit function.
In Proc. 57th FOCS, pp. 89–98. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.19] 9
[22] Michael A. Forbes and Zander Kelley: Pseudorandom generators for read-once branch-
ing programs, in any order. In Proc. 59th FOCS, pp. 946–955. IEEE Comp. Soc., 2018.
[doi:10.1109/FOCS.2018.00093] 13
[23] Lance Fortnow: Comparing notions of full derandomization. In Proc. 16th IEEE Conf. on Com-
put. Complexity (CCC’01), pp. 28–34. IEEE Comp. Soc., 2001. [doi:10.1109/CCC.2001.933869]
11
[24] Oded Goldreich: On promise problems: A survey. In Oded Goldreich, Arnold L.
Rosenberg, and Alan L. Selman, editors, Theoretical Computer Science, Essays in Memory of
Shimon Even, pp. 254–290. Springer, 2006. [doi:10.1007/11685654_12] 2
[25] Oded Goldreich: A sample of samplers: A computational perspective on sampling. In
Oded Goldreich, editor, Studies in Complexity and Cryptography. Miscellanea on the Interplay
between Randomness and Computation, pp. 302–332. Springer, 2011. [doi:10.1007/978-3-642-
22670-0_24] 51
[26] Oded Goldreich, Shafi Goldwasser, and Silvio Micali: How to construct random functions.
J. ACM, 33(4):792–807, 1986. [doi:10.1145/6490.6503] 30
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 56
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
[27] Oded Goldreich and Avi Wigderson: On derandomizing algorithms that err extremely
rarely. In Proc. 46th STOC, pp. 109–118. ACM Press, 2014. [doi:10.1145/2591796.2591808] 54
[28] Oded Goldreich and Avi Wigderson: On the size of depth-three boolean circuits for
computing multilinear functions. In Oded Goldreich, editor, Comput. Complexity and
Property Testing, LNCS 12050, pp. 41–86. Springer Cham, 2020. (2013). [ECCC:TR13-043] 10
[29] Johan Håstad: Computational limitations of small-depth circuits. Ph. D. thesis, MIT, 1986.
Available on author’s website, published as a book by MIT Press, 1987. 10
[30] Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby: A pseudo-
random generator from any one-way function. SIAM J. Comput., 28(4):1364–1396, 1999.
[doi:10.1137/S0097539793244708] 8, 22, 28, 29
[31] Alexander Healy, Salil P. Vadhan, and Emanuele Viola: Using nondeterminism to amplify
hardness. SIAM J. Comput., 35(4):903–931, 2006. [doi:10.1137/S0097539705447281] 41, 50,
51, 52
[32] Shuichi Hirahara: Non-black-box worst-case to average-case reductions within NP. In
Proc. 59th FOCS, pp. 247–258. IEEE Comp. Soc., 2018. [doi:10.1109/FOCS.2018.00032] 4, 5,
15, 18, 25, 30, 31, 48, 49
[33] Shuichi Hirahara: Characterizing average-case complexity of PH by worst-
case meta-complexity. In Proc. 61st FOCS, pp. 50–60. IEEE Comp. Soc., 2020.
[doi:10.1109/FOCS46700.2020.00014] 7
[34] Shuichi Hirahara: Non-disjoint promise problems from meta-computational view
of pseudorandom generator constructions. In Proc. 35th Comput. Complexity Conf.
(CCC’20), pp. 20:1–47. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020.
[doi:10.4230/LIPIcs.CCC.2020.20] 1
[35] Shuichi Hirahara: Unexpected hardness results for Kolmogorov complexity un-
der uniform reductions. In Proc. 52nd STOC, pp. 1038–1051. ACM Press, 2020.
[doi:10.1145/3357713.3384251] 5, 7, 8, 15, 22
[36] Shuichi Hirahara, Igor Carboni Oliveira, and Rahul Santhanam: NP-hardness of
Minimum Circuit Size Problem for OR-AND-MOD circuits. In Proc. 33rd Comput. Complexity
Conf. (CCC’18), pp. 5:1–31. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018.
[doi:10.4230/LIPIcs.CCC.2018.5] 15
[37] Shuichi Hirahara and Rahul Santhanam: On the average-case complexity of MCSP
and its variants. In Proc. 32nd Comput. Complexity Conf. (CCC’17), pp. 7:1–20. Schloss
Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.CCC.2017.7] 11, 15,
30
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 57
S HUICHI H IRAHARA
[38] Shuichi Hirahara and Osamu Watanabe: Limits of Minimum Circuit Size Problem as
oracle. In Proc. 31st Comput. Complexity Conf. (CCC’16), pp. 18:1–20. Schloss Dagstuhl–
Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.18] 7, 15
[39] Shuichi Hirahara and Osamu Watanabe: On nonadaptive security reductions of hit-
ting set generators. In Proc. 24th Internat. Conf. on Randomization and Computation
(RANDOM’20), pp. 15:1–14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020.
[doi:10.4230/LIPIcs.APPROX/RANDOM.2020.15] 4
[40] John M. Hitchcock and Aduri Pavan: On the NP-completeness of the Minimum
Circuit Size Problem. In Proc. 35th Found. Softw. Techn. Theoret. Comp. Sci. Conf.
(FSTTCS’15), pp. 236–245. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015.
[doi:10.4230/LIPIcs.FSTTCS.2015.236] 7
[41] Russell Impagliazzo: Hard-core distributions for somewhat hard problems. In Proc. 36th
FOCS, pp. 538–545. IEEE Comp. Soc., 1995. [doi:10.1109/SFCS.1995.492584] 3
[42] Russell Impagliazzo: A personal view of average-case complexity. In Proc. 10th IEEE
Conf. Structure in Complexity Theory (SCT’95), pp. 134–147. IEEE Comp. Soc., 1995.
[doi:10.1109/SCT.1995.514853] 53
[43] Russell Impagliazzo: Relativized separations of worst-case and average-case complexities
for NP. In Proc. 26th IEEE Conf. on Comput. Complexity (CCC’11), pp. 104–114. IEEE Comp.
Soc., 2011. [doi:10.1109/CCC.2011.34] 4
[44] Russell Impagliazzo and Avi Wigderson: P = BPP if E requires exponential circuits:
Derandomizing the XOR lemma. In Proc. 29th STOC, pp. 220–229. ACM Press, 1997.
[doi:10.1145/258533.258590] 3, 11, 12, 17, 19, 41, 51
[45] Valentine Kabanets and Jin-yi Cai: Circuit minimization problem. In Proc. 32nd STOC, pp.
73–79. ACM Press, 2000. [doi:10.1145/335305.335314] 15
[46] Richard M. Karp and Richard J. Lipton: Turing machines that take advice. Enseign. Math.,
28:191–209, 1982. [doi:10.5169/seals-52237] 9, 33
[47] Adam R. Klivans and Rocco A. Servedio: Boosting and hard-core set construction. Machine
Learning, 51(3):217–238, 2003. [doi:10.1023/A:1022949332276] 53
[48] Adam R. Klivans and Dieter van Melkebeek: Graph nonisomorphism has subexponential
size proofs unless the Polynomial-time Hierarchy collapses. SIAM J. Comput., 31(5):1501–
1526, 2002. [doi:10.1137/S0097539700389652] 3, 13, 35, 37
[49] Ker-I Ko: On the complexity of learning minimum time-bounded Turing machines. SIAM
J. Comput., 20(5):962–986, 1991. [doi:10.1137/0220059] 7
[50] Leonid A. Levin: Randomness conservation inequalities; Information and independence in
mathematical theories. Inform. Control, 61(1):15–37, 1984. [doi:10.1016/S0019-9958(84)80060-
1] 9, 32
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 58
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
[51] Leonid A. Levin: Average case complete problems. SIAM J. Comput., 15(1):285–286, 1986.
[doi:10.1137/0215020] 4
[52] William J. Masek: Some NP-complete set covering problems. Master’s thesis, MIT CS Lab,
1978. Cited in the NP-completeness column by David Johnson. 15
[53] Dylan M. McKay, Cody D. Murray, and R. Ryan Williams: Weak lower bounds on
resource-bounded compression imply strong separations of complexity classes. In Proc.
51st STOC, pp. 1215–1225. ACM Press, 2019. [doi:10.1145/3313276.3316396] 16
[54] Cody D. Murray and R. Ryan Williams: On the (non) NP-hardness of computing circuit
complexity. Theory of Computing, 13(4):1–22, 2017. [doi:10.4086/toc.2017.v013a004] 7
[55] Noam Nisan: Pseudorandom generators for space-bounded computation. Combinatorica,
12(4):449–461, 1992. [doi:10.1007/BF01305237] 12
[56] Noam Nisan and Avi Wigderson: Hardness vs randomness. J. Comput. System Sci.,
49(2):149–167, 1994. [doi:10.1016/S0022-0000(05)80043-1] 3, 23, 32, 37, 38, 48
[57] Igor Carboni Oliveira, Ján Pich, and Rahul Santhanam: Hardness magnification near
state-of-the-art lower bounds. Theory of Computing, 17(11):1–38, 2021. Preliminary version
in CCC’19. [doi:10.4086/toc.2021.v017a011] 16
[58] Igor Carboni Oliveira and Rahul Santhanam: Hardness magnification for natural prob-
lems. In Proc. 59th FOCS, pp. 65–76. IEEE Comp. Soc., 2018. [doi:10.1109/FOCS.2018.00016]
10, 15, 16
[59] Rafail Ostrovsky: One-way functions, hard on average problems, and statistical zero-
knowledge proofs. In Proc. 6th IEEE Conf. Structure in Complexity Theory (SCT’91), pp.
133–138. IEEE Comp. Soc., 1991. [doi:10.1109/SCT.1991.160253] 31
[60] Aduri Pavan, Rahul Santhanam, and N. V. Vinodchandran: Some results on average-case
hardness within the Polynomial Hierarchy. In Proc. 26th Found. Softw. Techn. Theoret. Comp.
Sci. Conf. (FSTTCS’06), pp. 188–199. Springer, 2006. [doi:10.1007/11944836_19] 6
[61] Ran Raz, Omer Reingold, and Salil P. Vadhan: Extracting all the randomness and
reducing the error in Trevisan’s extractors. J. Comput. System Sci., 65(1):97–128, 2002.
[doi:10.1006/jcss.2002.1824] 48
[62] Alexander A. Razborov: Lower bounds on the size of bounded depth circuits over a
complete basis with logical addition. Math. Notes. Acad. Sci. USSR (English translation),
41(4):333–338, 1987. [doi:10.1007/BF01137685] 11
[63] Alexander A. Razborov and Steven Rudich: Natural Proofs. J. Comput. System Sci.,
55(1):24–35, 1997. [doi:10.1006/jcss.1997.1494] 15, 16, 17, 30
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 59
S HUICHI H IRAHARA
[64] Omer Reingold, Luca Trevisan, and Salil P. Vadhan: Notions of reducibility between
cryptographic primitives. In Proc. Theory of Cryptography Conf. (TCC’04), pp. 1–20. Springer,
2004. [doi:10.1007/978-3-540-24638-1_1] 18
[65] Rahul Santhanam: Pseudorandomness and the Minimum Circuit Size Problem. In Proc.
11th Innovations in Theoret. Comp. Sci. Conf. (ITCS’20), pp. 68:1–26. Schloss Dagstuhl–Leibniz-
Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.ITCS.2020.68] 15
[66] Ronen Shaltiel and Emanuele Viola: Hardness amplification proofs require majority.
SIAM J. Comput., 39(7):3122–3154, 2010. [doi:10.1137/080735096] 11
[67] Madhu Sudan: Decoding of Reed Ssolomon codes beyond the error-correction bound. J.
Complexity, 13(1):180–193, 1997. [doi:10.1006/jcom.1997.0439] 22
[68] Madhu Sudan, Luca Trevisan, and Salil P. Vadhan: Pseudorandom generators without
the XOR lemma. J. Comput. System Sci., 62(2):236–266, 2001. [doi:10.1006/jcss.2000.1730] 3,
4, 12, 15, 35, 42, 43
[69] Boris A. Trakhtenbrot: A survey of Russian approaches to Perebor (brute-force
searches) algorithms. IEEE Annals of the History of Computing, 6(4):384–400, 1984.
[doi:10.1109/MAHC.1984.10036] 15
[70] Luca Trevisan: List-decoding using the XOR lemma. In Proc. 44th FOCS, pp. 126–135. IEEE
Comp. Soc., 2003. [doi:10.1109/SFCS.2003.1238187] 52
[71] Luca Trevisan and Salil P. Vadhan: Pseudorandomness and average-case complexity via
uniform reductions. Comput. Complexity, 16(4):331–364, 2007. [doi:10.1007/s00037-007-
0233-x] 4
[72] Luca Trevisan and Tongke Xue: A derandomized Switching Lemma and an improved
derandomization of AC0. In Proc. 28th IEEE Conf. on Comput. Complexity (CCC’13), pp.
242–247. IEEE Comp. Soc., 2013. [doi:10.1109/CCC.2013.32] 54
[73] Salil P. Vadhan: An unconditional study of Computational Zero Knowledge. SIAM J.
Comput., 36(4):1160–1214, 2006. [doi:10.1137/S0097539705447207] 31
[74] Salil P. Vadhan: Pseudorandomness. Found. Trends Theor. Comp. Sci., 7(1–3):1–336, 2012.
[doi:10.1561/0400000010] 22, 23, 24, 42
[75] Leslie G. Valiant and Vijay V. Vazirani: NP is as easy as detecting unique solutions.
Theoret. Comput. Sci., 47:85–93, 1986. [doi:10.1016/0304-3975(86)90135-0] 2
[76] Emanuele Viola: The complexity of constructing pseudorandom generators from hard
functions. Comput. Complexity, 13(3–4):147–188, 2005. [doi:10.1007/s00037-004-0187-1] 4, 37
[77] Andrew Chi-Chih Yao: Theory and applications of trapdoor functions (extended abstract).
In Proc. 23rd FOCS, pp. 80–91. IEEE Comp. Soc., 1982. [doi:10.1109/SFCS.1982.45] 3, 29
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 60
N ON -D ISJOINT P ROMISE P ROBLEMS FROM P SEUDORANDOM G ENERATOR C ONSTRUCTIONS
[78] Sergey Yekhanin: Locally decodable codes. Found. Trends Theor. Comp. Sci., 6(3):139–255,
2012. [doi:10.1561/0400000030] 42
AUTHOR
Shuichi Hirahara
Associate professor
Principles of Informatics Research Division
National Institute of Informatics
Tokyo, Japan
s_hirahara nii ac jp
https://researchmap.jp/shuichi.hirahara?lang=en
ABOUT THE AUTHOR
Shuichi Hirahara is an Associate Professor at the National Institute of Informatics,
Japan. He obtained his Ph. D. from the University of Tokyo under the supervision
of Hiroshi Imai in 2019. After joining the National Institute of Informatics
as an Assistant Professor, he was promoted to an Associate Professor in 2022.
He is interested in average-case complexity, meta-complexity, and Kolmogorov
complexity.
T HEORY OF C OMPUTING, Volume 19 (4), 2023, pp. 1–61 61