# On Hardness Assumptions Needed for “Extreme High-End” PRGs and Fast
Derandomization

Ronen Shaltiel Department of computer science, University of Haifa. E-mail:
<EMAIL_ADDRESS>This research was supported by ISF grants 1628/17 and
1006/23. Emanuele Viola Khoury College of Computer Sciences, Northeastern
University, E-mail<EMAIL_ADDRESS>Supported by NSF CCF award 1813930 and
NSF CCF award 2114116.

The hardness vs. randomness paradigm aims to explicitly construct pseudorandom
generators $G:\\{0,1\\}^{r}\to\\{0,1\\}^{m}$ that fool circuits of size $m$,
assuming the existence of explicit hard functions. A “high-end PRG” with seed
length $r=O(\log m)$ (implying BPP=P) was achieved in a seminal work of
Impagliazzo and Wigderson (STOC 1997), assuming the high-end hardness
assumption: there exist constants $0<\beta<1<B$, and functions computable in
time $2^{B\cdot n}$ that cannot be computed by circuits of size $2^{\beta\cdot
n}$.

Recently, motivated by fast derandomization of randomized algorithms, Doron et
al. (FOCS 2020) and Chen and Tell (STOC 2021), construct “extreme high-end
PRGs” with seed length $r=(1+o(1))\cdot\log m$, under qualitatively stronger
assumptions.

We study whether extreme high-end PRGs can be constructed from the following
scaled version of the assumption which we call the extreme high-end hardness
assumption, and in which $\beta=1-o(1)$ and $B=1+o(1)$. We give a partial
negative answer:

  * •

Doron et al. compose a PEG (pseudo-entropy generator) with an extractor. The
PEG is based on a hardness assumption for MA-type circuits. We show that
black-box PEG constructions from the extreme high-end hardness assumption must
have large seed length (and so cannot be used to obtain extreme high-end PRGs
by applying an extractor).

To prove this, we establish a new property of (general) black-box PRG
constructions from hard functions: it is possible to fix many output bits of
the construction while fixing few bits of the hard function. This property
distinguishes PRG constructions from typical extractor constructions, and this
may explain why it is difficult to design PRG constructions.

  * •

Chen and Tell compose two PRGs: $G_{1}:\\{0,1\\}^{(1+o(1))\cdot\log
m}\to\\{0,1\\}^{r_{2}=m^{\Omega(1)}}$ and
$G_{2}:\\{0,1\\}^{r_{2}}\to\\{0,1\\}^{m}$. The first PRG is based on the
extreme high-end hardness assumption, and the second PRG needs to run in time
$m^{1+o(1)}$, and is based on one way functions. We show that in black-box
proofs of hardness amplification to $\frac{1}{2}+1/m$, reductions must make
$\Omega(m)$ queries, even in the extreme high-end. Known PRG constructions
from hard functions are black-box and use (or imply) hardness amplification,
and so cannot be used to construct a PRG $G_{2}$ from the extreme high-end
hardness assumption.

The new feature of our hardness amplification result is that it applies even
to the extreme high-end setting of parameters, whereas past work does not. Our
techniques also improve recent lower bounds of Ron-Zewi, Shaltiel and Varma
(ITCS 2021) on the number of queries of local list-decoding algorithms.

##  1 Introduction

###  1.1 Background

The hardness vs. randomness paradigm (initiated in [Yao82, BM84, NW94] and
followed up by a long sequence of work [BFNW93, Imp95, IW97, STV01, KvM02,
MV05, ISW99, ISW06, SU05, Uma03, Uma09, SU06, AIKS16, DMOZ20, CT21b, CT21a])
aims to explicitly construct pseudorandom generators (PRGs) from explicit hard
functions.

######  Definition 1.1 (PRGs).

A function $G:\\{0,1\\}^{r}\to\\{0,1\\}^{m}$ is an $\epsilon$-PRG for a
function $D:\\{0,1\\}^{m}\rightarrow\\{0,1\\}$, if

$|\Pr[D(G(U_{r}))=1]-\Pr[D(U_{m})=1]|\leq\epsilon.$

$G$ is an $\epsilon$-PRG for a class $\mathcal{D}$ of functions
$D:\\{0,1\\}^{m}\to\\{0,1\\}$, if for every $D$ in $\mathcal{D}$, $G$ is an
$\epsilon$-PRG for $D$. If we omit $\epsilon$ or $\mathcal{D}$, the default
choices are $\epsilon=1/10$, and $\mathcal{D}$ is the class of circuits of
size $m$.

Explicit pseudorandom generators have many applications in computer science.
The signature application of PRGs is to derandomize randomized algorithms (by
running the algorithm using all outputs of the PRG). This is quantitatively
specified in the proposition below.

######  Proposition 1.2 (standard).

If $G:\\{0,1\\}^{r}\to\\{0,1\\}^{m}$ is a PRG, then every randomized algorithm
running in time $m$ can be simulated by a deterministic algorithm in time
$\operatorname{Time}_{\operatorname{all}}(G)+2^{r}\cdot m$, where
$\operatorname{Time}_{\operatorname{all}}(G)$ is the time it takes to compute
the output of $G$ on all $2^{r}$ inputs, and is obviously upper bounded by
$2^{r}\cdot\operatorname{Time}(G)$, where $\operatorname{Time}(G)$ is the time
it takes to compute $G$ on a given input.

##### High-end PRGs that imply BPP=P.

A corollary of Proposition 1.2 is that a PRG $G:\\{0,1\\}^{r=O(\log
m)}\to\\{0,1\\}^{m}$ with $\operatorname{Time}(G)=\operatorname{poly}(m)$
implies that BPP=P.111Note that in this range of parameters there is no reason
to distinguish between $\operatorname{Time}(G)$ and
$\operatorname{Time}_{\operatorname{all}}(G)$, as
$\operatorname{Time}_{\operatorname{all}}(G)=\operatorname{poly}(m)$ if and
only if $\operatorname{Time}(G)=\operatorname{poly}(m)$, and this is why past
work is stated in terms of $\operatorname{Time}(G)$ and not
$\operatorname{Time}_{\operatorname{all}}(G)$.

Such PRGs are often referred to as _“high-end PRGs”_. Historically, this name
aims to distinguish them from weaker _”low-end PRGs”_ which have $r=m^{o(1)}$,
and $\operatorname{Time}(G)=2^{O(r)}$, which in turn imply the weaker
conclusion that BPP is in subexponential time, see [ISW06, SU05] for a
discussion.

##### Extreme high-end PRGs and fast derandomization.

Recently, Doron et al. [DMOZ20] asked whether it is possible to obtain a
faster derandomization. Here, the goal is to show that a randomized algorithm
running in time $m$ can be simulated by a deterministic algorithm running in
time $O(m^{c})$ for the smallest possible constant $c$.

The time of the deterministic simulation of Theorem 1.2 depends on both the
seed length $r$, and $\operatorname{Time}_{\operatorname{all}}(G)$. Note that
even if we take $r$ to the extreme222A PRG must have $r\geq\log m-O(\log\log
m)$ as otherwise, a circuit of size $m$ could be hardwired with prefixes of
length $r+1$ for all $2^{r}$ pseudorandom strings, and distinguish a uniform
string from a pseudorandom string., and have a PRG with $r=1\cdot\log m$, then
the time of the simulation is at least $2^{r}\cdot m=m^{2}$. This time can be
achieved if furthermore,
$\operatorname{Time}_{\operatorname{all}}(G)=O(2^{r}\cdot m)=O(m^{2})$ (which
follows if $\operatorname{Time}(G)=O(m)$). This means that we can hope to
achieve $c=2$ (that is, a quadratic time simulation) if we have such PRGs,
which we will call _“extreme high-end”_ PRGs.

######  Definition 1.3 (Extreme high-end PRGs).

$G:\\{0,1\\}^{r}\to\\{0,1\\}^{m}$ is an extreme high-end PRG if:

Pseudorandomness: $G$ is a PRG with seed length $r=(1+o(1))\cdot\log m$.

Explicitness: $\operatorname{Time}_{\operatorname{all}}(G)=m^{2+o(1)}$ (which
follows if $\operatorname{Time}(G)=m^{1+o(1)}$).

These parameters are chosen so that an extreme high-end PRG implies that
randomized algorithms running in time $m$ can be simulated deterministically
in time $m^{2+o(1)}$.

There are reasons to think that this quadratic slowdown is the best possible
if one seeks the smallest possible $c$ such that every randomized algorithm
running in time $m$ can be simulated deterministic time $m^{c}$. More
precisely, the problem of “univariate identity testing” is in
BPTIME$(\tilde{O}(n))$ but not in DTIME$(n^{2-o(1)})$, under certain
assumptions on “fine grained complexity” introduced by Carmosino et al.
[CGI+16]. See [DMOZ20] for details and a discussion.

We remark that this lower bound still allows a deterministic simulation that
runs in time $O(m\cdot n)$ (where $n$ is the input length) and a simulation
that approaches this time bound was obtained by Chen and Tell [CT21b] under
certain hardness assumptions. See [CT21b] for details and a discussion.

##### Hardness implied by PRGs.

PRGs immediately imply circuit lower bounds that are beyond our current
ability. Consequently, constructing explicit PRGs, requires circuit lower
bounds (namely the existence of explicit functions that cannot be computed by
small circuits). In particular, high-end PRGs imply the existence of functions
$f:\\{0,1\\}^{\ell}\to\\{0,1\\}$ which cannot be computed by circuits of size
$2^{\Omega(\ell)}$, and $\operatorname{Time}(f)=2^{O(\ell)}$.333More
specifically, Impagliazzo, Shaltiel and Wigderson [ISW99] showed that if
$G:\\{0,1\\}^{r}\to\\{0,1\\}^{m}$ is a PRG then for $\ell=r+1$, there is a
function $f:\\{0,1\\}^{\ell}\to\\{0,1\\}$ (defined by checking whether an
input of length $\ell$ is a prefix of an output of $G$) such that $f$ cannot
be computed by circuits of size $m$, and
$\operatorname{Time}_{\operatorname{all}}(f)\approx\operatorname{Time}_{\operatorname{all}}(G)$.
Note that $\operatorname{Time}_{\operatorname{all}}(f)=2^{O(\ell)}$ iff
$\operatorname{Time}(f)=2^{O(\ell)}$.

####  1.1.1 The Impagliazzo-Wigderson (high-end) hardness assumption

The goal of the hardness vs. randomness program is to construct PRGs based on
lower bounds that are as strong (or almost as strong) as the ones implied by
the PRG. A major milestone in this program was achieved by Impagliazzo and
Wigderson [IW97].

######  Theorem 1.4 ([IW97]).

A high-end PRG follows from the following assumption:

The high-end hardness assumption: There exist constants $0<\beta<1<B$, and a
function $f:\\{0,1\\}^{\ell}\to\\{0,1\\}$ that satisfies:

Hardness: $f$ cannot be computed by circuits of size $2^{\beta\cdot\ell}$.

Explicitness: $\operatorname{Time}(f)\leq 2^{B\cdot\ell}$.

Theorem 1.4 converts hardness into pseudorandomness at close to the “correct
rate” (as in the converse direction) if one does not care about the precise
values of the constants $\beta,B$, and the constant hidden in the $O(\cdot)$
notation in the seed length of the high-end PRG.

####  1.1.2 Scaling the Impagliazzo-Wigderson assumption to the extreme high-
end

In the case of extreme high-end PRGs, we insist on seed length $r\approx
1\cdot\log m$ and the constants $\beta,B$ from the The high-end hardness
assumption do matter. Assuming that we don’t expect to “improve” the hardness
of the assumed explicit hard function, we must have $\beta\geq 1-o(1)$ and
$B\leq 1+o(1)$. Thus, imitating the approach of Impagliazzo and Wigderson
[IW97] for the extreme high-end, leads to the following open problem.

######  Open Problem 1.5.

Show that an extreme high-end PRG follows from the following assumption:

The extreme high-end hardness assumption: There exists a function
$f:\\{0,1\\}^{\ell}\to\\{0,1\\}$ that satisfies:

Hardness: $f$ cannot be computed by circuits of size $2^{(1-o(1))\cdot\ell}$.

Explicitness: $\operatorname{Time}(f)\leq 2^{(1+o(1))\cdot\ell}$.444In the
case of the extreme high-end, it does make sense to distinguish between
$\operatorname{Time}(f)$ and $\operatorname{Time}_{\operatorname{all}}(f)$,
and one can consider starting from a weaker explicitness condition in which it
is required that $\operatorname{Time}_{\operatorname{all}}(f)\leq
2^{(2+o(1))\cdot\ell}$.

The proof techniques of Impagliazzo and Wigderson [IW97] (as well as of later
works [STV01, SU05, Uma03]) do not solve Open Problem 1.5. As we explain in
Section 1.2.4, these proofs rely on the “hybrid argument” of [Yao82, GM84],
and even assuming the extreme high-end hardness assumption, one can at best
obtain a PRG $G:\\{0,1\\}^{r}\to\\{0,1\\}^{m}$ with seed length $r\geq
A\cdot\log m$, where $A>3$, and actual proofs do worse.

##### Recent work on extreme high-end PRGs.

Recently, Doron et al. [DMOZ20], and Chen and Tell [CT21b] gave conditional
constructions of extreme high-end PRGs, however, in both cases the assumption
used is _stronger_ than the extreme high-end hardness assumption. We will
elaborate on these results later on.555Both these papers aim for a slightly
weaker goal. Rather than requiring a single PRG with seed length
$r=(1+o(1))\cdot\log m$ and explicitness $m^{1+o(1)}$ as in Definition 1.3,
their constructions show that for every $\gamma>0$ there exists a PRG with
seed length $r=(1+\gamma)\cdot\log m$ and explicitness $m^{1+\gamma}$. We will
not distinguish these two goals in the informal discussion in the
introduction. An incomparable assumption was very recently used by Chen and
Tell [CT21a] for constructing “targeted PRGs” (which are weaker than PRGs and
yet suffice for derandomizing randomized algorithms).

##### Goals of this paper.

In this paper, we investigate the problem of constructing explicit PRGs from
explicit hard functions, focusing on open problem 1.5. More specifically, we
investigate the power of “black-box proofs” that convert explicit hard
functions into PRGs and related objects. We show limitations on certain recent
approaches to solve Open Problem 1.5, and hope that this may help to point us
in the direction of better constructions. A secondary goal of this paper is to
survey recent work and point out the relationship between parameters, and
potential barriers for improvement.

###  1.2 Black-box proofs

####  1.2.1 Black-box proofs for PRG constructions and hardness amplification

A black-box proof that converts hard functions into PRGs consists of two
parts:

  * •

A _construction map_. This is a map that given a candidate function
$f:\\{0,1\\}^{\ell}\to\\{0,1\\}$ produces a candidate PRG $\mathsf{Con}(f)$.
(To avoid clutter, we will denote the function $\mathsf{Con}(f)$ by
$\mathsf{Con}_{f}:\\{0,1\\}^{r}\to\\{0,1\\}^{m}$).

  * •

A _reduction_ establishing the correctness of the construction. This is an
oracle procedure $\mathsf{Red}^{(\cdot)}$ which given oracle access to an
adversary $D$ that breaks the security of $\mathsf{Con}_{f}$, implements an
adversary $C$ that breaks the security of $f$.

As we explain in Section 1.2.3, because of their combinatorial properties,
reductions of this type must be _nonuniform_ and receive a “nonuniform advice
string” $\alpha$ (that may depend on the candidate function $f$ and the
adversary $D$). This is reflected in the formal definition below.

We will consider “black-box $\mathsf{A}\Rightarrow\mathsf{B}$ proofs” for
several other choices of primitives $\mathsf{A,B}$ (and not just hard
functions and PRGs). One such primitive is functions that are hard on average
(meaning that small circuits cannot compute $f$ correctly with high
probability on a uniformly chosen input). Such functions can serve both as
$\mathsf{A}$ and $\mathsf{B}$ in black-box $\mathsf{A}\Rightarrow\mathsf{B}$
proofs. In order to capture all various scenarios in one definition, we will
use a terminology that will describe a primitive by what it means to “break
the security” of the primitive.

######  Definition 1.6.

Let $\mathcal{F}_{n,m}$ denote the set of all functions from $n$ bits to $m$
bits.

  * •

For $G\in\mathcal{F}_{r,m}$ and $D\in\mathcal{F}_{m,1}$, we say that $D$
$\epsilon$-$\mathsf{PRG}\mbox{-}\mathsf{breaks}$ $G$, if $G$ is not an
$\epsilon$-PRG for $D$.

  * •

For $f,C\in\mathcal{F}_{\ell,1}$, we say that $C$
$\rho$-$\mathsf{hard}\mbox{-}\mathsf{function}\mbox{-}\mathsf{breaks}$ $f$, if
$\Pr_{x\leftarrow U_{\ell}}[C(x)=f(x)]\geq\rho$. We say that $C$
$\mathsf{hard}\mbox{-}\mathsf{function}\mbox{-}\mathsf{breaks}$ $f$ if $C$
$1$-$\mathsf{hard}\mbox{-}\mathsf{function}\mbox{-}\mathsf{breaks}$ $f$
(meaning that $C=f$). We say that $f$ is a
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$ for $C$ if $C$ does not
$\rho$-$\mathsf{hard}\mbox{-}\mathsf{function}\mbox{-}\mathsf{breaks}$ $f$.

A ${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$ for circuits of a
certain size, is an average-case hard function, and the case where $\rho=1$
captures the previously considered notion of worst-case hard functions.

We now formally define black-box
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\epsilon}\mbox{-}\mathsf{PRG}$,
and
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\rho^{\prime}}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$
proofs.

######  Definition 1.7 (Black-box proofs).

Given parameters $\ell,r,m,a,\rho,\epsilon$ (resp.
$\ell,\ell^{\prime},a,\rho,\rho^{\prime}$) a black-box
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\epsilon}\mbox{-}\mathsf{PRG}$
proof (resp. a black-box
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\rho^{\prime}}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$
proof) is a pair $(\mathsf{Con},\mathsf{Red})$ of:

  * •

A construction map $\mathsf{Con}:\mathcal{F}_{\ell,1}\to\mathcal{F}_{r,m}$
(resp. $\mathsf{Con}:\mathcal{F}_{\ell,1}\to\mathcal{F}_{\ell^{\prime},1}$).
(We use $\mathsf{Con}_{f}$ to denote the function $\mathsf{Con}(f)$).

  * •

An oracle procedure $\mathsf{Red}^{(\cdot)}(x,\alpha)$ such that:

For every $f\in\mathcal{F}_{\ell,1}$ and for every $D\in\mathcal{F}_{m,1}$
such that $D$ $\epsilon$-$\mathsf{PRG}\mbox{-}\mathsf{breaks}$
$\mathsf{Con}_{f}$
(resp. for every $D\in\mathcal{F}_{\ell^{\prime},1}$ such that $D$
$\rho^{\prime}$-$\mathsf{hard}\mbox{-}\mathsf{function}\mbox{-}\mathsf{breaks}$
$\mathsf{Con}_{f}$),

there exists $\alpha\in\\{0,1\\}^{a}$, such that the function
$C\in\mathcal{F}_{\ell,1}$ defined by $C(x)=\mathsf{Red}^{D}(x,\alpha)$,
$\rho$-$\mathsf{hard}\mbox{-}\mathsf{function}\mbox{-}\mathsf{breaks}$ $f$.

If we omit $\rho$, we mean $\rho=1$. If we omit $\epsilon$, we mean
$\epsilon=1/10$. We say that $\mathsf{Red}$ makes $q$ queries, if for every
$D\in\mathcal{F}_{m,1}$, $\alpha\in\\{0,1\\}^{a}$, and $x\in\\{0,1\\}^{\ell}$,
$\mathsf{Red}^{D}(x,\alpha)$ makes at most $q$ oracle queries.

####  1.2.2 Parameters of black-box proofs

To the best of our knowledge all hardness vs. randomness proofs of PRG
constructions are black-box (or rely on components which are black-box). In a
black-box proof, the advice length $a$ and the number of queries $q$ determine
the “hardness loss” in the tradeoff. More specifically:

######  Proposition 1.8 (Number of queries determines hardness loss in black-
box proofs).

Let $(\mathsf{Con},\mathsf{Red})$ be a black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ (resp.
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\rho^{\prime}}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$)
proof in which $\mathsf{Red}$ makes $q$ queries, and has advice length $a$. If
we start from a function $f:\\{0,1\\}^{\ell}\to\\{0,1\\}$ that cannot be
computed by circuits of size $s$, and apply the black-box proof, one can at
best obtain that $\mathsf{Con}_{f}$ is a $\mathsf{PRG}$ (resp.
$\rho^{\prime}$-$\mathsf{hard}\mbox{-}\mathsf{function}$) for circuits of size
$m\leq\frac{s-a}{q}\leq\frac{s}{q}$.

Loosely speaking, Proposition 1.8 follows because, when measuring the size $s$
of the circuit $C=\mathsf{Red}^{D}(\cdot,\alpha)$ that is implied by the
reduction for a circuit $D$ of size $m$, then this circuit is of size $q\cdot
m+a$. This gives that $s\geq q\cdot m+a$, implying the proposition.

Every function $f:\\{0,1\\}^{\ell}\to\\{0,1\\}$ has circuits of size
$2^{\ell}$. This means that in order for reductions to be useful in
transforming hard-functions into PRGs (or average case hard functions) they
must make $q\leq\frac{s-a}{m}\leq\frac{2^{\ell}-a}{m}$ queries, and are
useless for this purpose, if $q\geq 2^{\ell}$. Moreover, in the extreme high-
end, $m=2^{(1-o(1))\cdot\ell}$ and so it is critical that
$q\leq\frac{s}{m}\leq\frac{2^{\ell}}{m}=2^{o(\ell)}=m^{o(1)}\ll m$.

##### Our notion of black-box does not guarantee explicitness.

We place no limitation on the map $\mathsf{Con}$, and so, the notion of black-
box that we use, _does not_ enforce that if $f$ can be computed efficiently,
then $\mathsf{Con}_{f}$ can be computed efficiently. This notion of black-box
does not imply the _explicitness_ of the constructed function
$\mathsf{Con}_{f}$. We make this choice, because we want to show impossibility
results on black-box proofs, and this choice makes our results stronger.666One
way to preserve efficiency is to require that there is an oracle machine
$A^{(\cdot)}$ (in some complexity class) such that for every
$f\in\mathcal{F}_{\ell,1}$, $A^{f}$ implements $\mathsf{Con}_{f}$. See e.g.,
[Vio05]. We also remark that the terms ”black-box” and “non-black-box” are
used to mean many different things in the literature.777For example, sometimes
the term “non-black-box” is used to denote a deterministic simulation of
randomized algorithms that is tailored for the specific input supplied to the
algorithm. This notion is used for example in the recent work of Chen and Tell
[CT21a] which constructs “targeted-PRGs” that are targeted to the given input,
and is unrelated to the notion of “black-box” used here.

##### Parameters for black-box proofs for the extreme high-end.

As a consequence of Proposition 1.8, if we assume the extreme high-end
hardness assumption, to obtain an extreme high-end PRG (as in Open Problem
1.5) using a black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proof, we
first need to solve the following open problem:

######  Open Problem 1.9.

Does there exist a black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proof with:

Seed length: $r=(1+o(1))\cdot\ell$. (Any black-box proof must have
$r\geq\ell$).

Output length: $m=2^{(1-o(1))\cdot\ell}$. (Any black-box proof must have
$m\leq 2^{\ell}$).

Advice string length: $a=m^{1+o(1)}=2^{(1-o(1))\cdot\ell}$. (Any black-box
proof must have $a\geq m$).

Number of queries: $q=m^{o(1)}=2^{o(\ell)}$.

We stress again that a positive answer to Open Problem 1.9 is a _necessary_
condition for using a black-box proofs to construct an extreme high-end PRG
from the extreme high-end hardness assumption, however, it is not a
_sufficient_ condition.

We do not know whether black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proofs as in
Open Problem 1.9 exist.888In fact, the only known lower bound on black-box
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\epsilon}\mbox{-}\mathsf{PRG}$
proofs by Shaltiel, Grinberg and Viola [GSV18] shows that if $a\leq
2^{\nu\cdot\ell}$ for some constant $\nu>0$, and $\rho<1-2^{-\ell}$ is
sufficiently larger than $\frac{1}{2}+\epsilon$ then
$q\geq\Omega(\frac{\log(1/(1-\rho))}{\epsilon^{2}})$. In the case of interest
where $\rho=1$ and $\epsilon$ is constant, this gives a weak bound of
$q\geq\Omega(\ell)$, and even this does not apply in the extreme high-end
where $a=2^{(1-o(1))\cdot\ell}$. Moreover, if we start from average-case
hardness, it is open to prove that $q>1$ for a black-box
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\epsilon}\mbox{-}\mathsf{PRG}$
proofs with $\rho\leq\frac{1}{2}+\epsilon$, even for small $a$. In Section 1.3
we show obstacles on certain approaches to design a black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proof, meeting
the parameters of Open Problem 1.9. More specifically, we show that certain
approaches cannot yield reductions with few queries. Before we describe our
results, we give more background on black-box proofs.

####  1.2.3 Black-box proofs as codes, extractors, and other applications

Black-boxness is often helpful in PRG constructions (as demonstrated in [NW94,
KvM02, MV05, SU05]) as such proofs readily extend to other computational
models (e.g, bounded depth circuits, or nondeterministic circuits). There are
other motivations to study black-box proofs (in addition to PRG constructions
and hardness amplification). In fact, in the connections and applications
below, the “black-boxness” of the proofs is crucial and helpful.

##### List-decodable codes.

Following Sudan, Trevisan and Vadhan [STV01], a Black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\rho^{\prime}}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$
proof $(\mathsf{Con},\mathsf{Red})$ yields a “list-decodable code”
$E:\\{0,1\\}^{2^{\ell}}\to\\{0,1\\}^{2^{\ell^{\prime}}}$, defined by
$E(f)_{y}=\mathsf{Con}_{f}(y)$. A consequence of lower bounds on the rate of
such codes is that $\ell^{\prime}\geq\ell+2\cdot\log(1/\rho^{\prime})$, and
that $a\geq 2\cdot\log(1/\rho^{\prime})$. Viewing the reduction as a “list” of
$2^{a}$ procedures (one for every advice string $\alpha\in\\{0,1\\}^{a}$)
yields a variant of a “local list-decoding algorithm” for the defined code,
with the same number of queries. Techniques developed for black-box proofs
[SV10, GSV18, AASY16] have been useful in proving lower bounds on the number
of queries of such codes [RSV21].

##### Randomness Extractors:

Following Trevisan [Tre01], a black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\epsilon}\mbox{-}\mathsf{PRG}$
proof $(\mathsf{Con},\mathsf{Red})$ yields a “randomness extractor”
$E:\\{0,1\\}^{2^{\ell}}\times\\{0,1\\}^{r}\to\\{0,1\\}^{m}$, defined by
$E(f,y)=\mathsf{Con}_{f}(y)$, and extracting randomness from sources with min-
entropy $k=a+\log(1/\epsilon)+O(1)$. A consequence of lower bounds on
extractors [RTS00] is that $r\geq\ell+2\cdot\log(1/\epsilon)$, and that $a\geq
m+\log(1/\epsilon)-O(1)$. Continuing the analogy of the previous item, the
reduction can be viewed as a local list-decoding algorithm for an “extractor-
code” [TZ04]. Local list-decoding algorithms for (standard) codes, and for
extractor-codes are closely related to “hard-core bits” for cryptographic
primitives (see e.g. [RSV21] for a discussion).

##### Other applications.

In recent years, black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proofs have
found numerous applications in areas that are not directly related to
pseudorandomness, and rely on “black-boxness”. Some examples are: Learning and
compression algorithms (Carmosino et al. [CIKK16] and subsequent work), worst-
case to average-case reductions within NP (Hirahara [Hir18] and subsequent
work), and Kolmogorov Complexity (Allender et al. [ABK+06] and subsequent
work).

####  1.2.4 Black-box proofs and the hybrid argument

##### The hybrid argument cannot be used in the extreme high-end.

Most known black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proofs in the
literature rely on _hardness amplification_ in order to use the _hybrid
argument_ of [Yao82, GM84]. That is, to achieve an $\epsilon$-PRG, the
construction is a sequence of two black-box proofs:
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow(\frac{1}{2}+\frac{\epsilon}{m})\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\epsilon\mbox{-}\mathsf{PRG}$.
Thus, even for constant $\epsilon$, hardness amplification must be performed
to $\rho^{\prime}\leq(\frac{1}{2}+\frac{1}{m})$. By the bounds in Section
1.2.3, in the first step, a function $f_{1}$ with input length $\ell$ must be
transformed into a function $f^{\prime}$ with input length
$\ell^{\prime}\geq\ell+2\cdot\log\frac{1}{\rho^{\prime}}\geq\ell+2\log m$. The
final PRG construction will have seed length $r\geq\ell^{\prime}\geq\ell+2\log
m\geq 3\log m$. This is too large in the extreme high end, where we want
$r=(1+o(1))\cdot\log m$.

##### The hybrid argument suffices for the high-end.

We remark that taking $\ell^{\prime}=O(\ell+\log m)$ and $r=O(\ell^{\prime})$
does suffice for the (non-extreme) high-end, and this is how known
constructions for the high-end [IW97, STV01, SU05, Uma03] are achieved.999More
specifically, hardness amplification can be performed (by a black-box proof)
using “local list-decodable codes” [STV01], and the second
${(\frac{1}{2}+\frac{\epsilon}{m})}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$
step is done using the Nisan-Wigderson generator [NW94], which is a black-box
proof. Shaltiel and Umans [SU05] and Umans [Uma03] gave an alternative direct
transformation from worst-case hard function into PRGs which achieves a better
seed length in the “low-end”. However, as it also relies on the hybrid
argument (and implies hardness amplification), it cannot achieve the extreme
high-end.

###  1.3 Our Results

We show that certain approaches cannot yield a black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proof with the
parameters of Open Problem 1.9, and therefore cannot be used to solve Open
Problem 1.5. Our results are summarized in Table 1 and Table 2.

Table 1: Black-box proofs for PRGs and PEGs Result | Type | Range | Condition | Bound
---|---|---|---|---
[GSV18] | $\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\epsilon}\mbox{-}\mathsf{PRG}$ | $a\leq 2^{\nu\cdot\ell}$ |  | $q\geq\Omega(\frac{\ell}{\epsilon^{2}})$
Thm 1.11 |  $\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\epsilon}\mbox{-}\mathsf{PRG}$, constant $\epsilon$ | $a\leq\nu\cdot 2^{\ell}$ | $\exists j=o(\frac{2^{\ell}}{\ell}):\operatorname{Fix}_{j}(\mathsf{Con})>a+j\cdot\ell)$ | $q\geq 2^{\ell}$
Thm 1.14 |  $\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\epsilon$-$\mathsf{PEG}$, constant $\epsilon$ | $a\leq\nu\cdot 2^{\ell}$ | $r<\ell-\log\ell-O(1)$ | $q\geq 2^{\ell}$
[IW97] |  $\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\epsilon}\mbox{-}\mathsf{PRG}$, constant $\epsilon$ | $a\leq 2^{\nu\cdot\ell}$ |  | $q\leq m^{\Theta(1)}$
Table 2: Black-box proofs for hardness amplification

Result | Type | Range | Bound
---|---|---|---
[GSV18] | $\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{(\frac{1}{2}+\epsilon)}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$ | $a\leq 2^{\nu\cdot\ell}$ | $q\geq\Omega(\frac{\ell}{\epsilon^{2}})$
Thm 1.15 | $\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{(\frac{1}{2}+\epsilon)}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$ | $a\leq\nu\cdot 2^{\ell}$ | $q\geq\Omega(\frac{1}{\epsilon})$
Thm 1.15 |  $\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{(\frac{1}{2}+\epsilon)}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$, constant $\epsilon$ | $a\leq\nu\cdot 2^{\ell}$ | $q\geq\Omega(\ell-\log(2a))$
[IW97, STV01] | $\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{(\frac{1}{2}+\epsilon)}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$ | $a\leq\nu\cdot 2^{\ell}$ | $q\leq\operatorname{poly}(\frac{\ell}{\epsilon})$

In both tables above the first three lines are lower bounds, while the last
line is an upper bound, and $0<\nu\leq\frac{1}{2}$ is some constant.

####  1.3.1 Limitations on constructions of black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proofs

We show that for any black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proof
$(\mathsf{Con},\mathsf{Red})$, if $\mathsf{Red}$ makes $q\leq 2^{\ell}$
queries, then $\mathsf{Con}$ must be structured in a way that allows “fixing
many outputs, with small information cost”. More precisely, we introduce a
measure $\operatorname{Fix}_{j}(\mathsf{Con})$ defined to be the minimal
number $h$, so that when $F$ is chosen at random from $\mathcal{F}_{\ell,1}$,
it is possible to fix $j$ outputs of $\mathsf{Con}_{F}$, while reducing the
information about $F$ by only $h$ bits of information.

######  Definition 1.10 (The cost of fixing $j$ outputs).

Given $\mathsf{Con}:\mathcal{F}_{\ell,1}\to\mathcal{F}_{r,m}$ we define
$\operatorname{Fix}_{j}(\mathsf{Con})$ to be the minimal number $h$ such that
there exist $j$ distinct outputs $z_{1},\ldots,z_{j}\in\\{0,1\\}^{m}$ such
that:

$\Pr_{F\leftarrow\mathcal{F}_{\ell,1}}[\forall i\in[j]:\exists
y_{i}\in\\{0,1\\}^{r}\mbox{ s.t. }\mathsf{Con}_{F}(y_{i})=z_{i}]\geq 2^{-h}.$

We show that if $\mathsf{Red}$ makes a small number $q$ of queries, then for
every $j$ that is not too large, $\operatorname{Fix}_{j}(\mathsf{Con})\leq
a+j\cdot(\log q+O(1))$. Loosely speaking, this means that after a “fixed cost”
of $a$ bits of information, a large number of outputs of $\mathsf{Con}_{F}$
can be fixed at the cost of roughly $\log q$ bits of information about $F$,
per $m$-bit output. This is stated formally below:

######  Theorem 1.11.

There exists a constant $\nu>0$ such that for every
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\epsilon}\mbox{-}\mathsf{PRG}$
proof $(\mathsf{Con},\mathsf{Red})$ with parameters $\ell,r,m,a\leq\nu\cdot
2^{\ell},\epsilon\leq 1-2^{r-m},\rho>0.51$, if $\mathsf{Red}$ makes $q\leq
2^{\ell}$ queries, then for every $j\leq\nu\cdot\frac{2^{\ell}}{\ell}$,

$\operatorname{Fix}_{j}(\mathsf{Con})\leq a+j\cdot(\log q+O(1))\leq
a+j\cdot(\ell+O(1)).$

Previous limitations on the number of queries for reductions in black-box
proofs (of any type) do not apply when $a\geq 2^{\ell/2}$ and therefore are
unapplicable in the extreme high-end

We stress that Theorem 1.11 is unrelated to the “hybrid argument” and applies
even for constructions where the correctness of the reduction _does not_ rely
on the hybrid argument. Moreover, the result applies for the whole range of
parameters, and regardless of the choices of seed length and output length.
See Section 3.1 for a more general statement and a discussion.

In the next section we use Theorem 1.11 to show limitations on the “PEG +
extractor” approach of [DMOZ20].

##### Distinction between black-box PRGs and typical extractors.

Following Trevisan [Tre01] (see discussion in Section 1.2.3) we know that
construction maps for black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proofs are
extractors (regardless of the number of queries used by the reduction). In
fact, extractors and black-box proofs are essentially equivalent if we do not
restrict the number of queries made by the reduction.

It is standard that if we choose a construction map $\mathsf{Con}$ at random,
it will be an extractor. Nevertheless, we show that it is unlikely that a
random construction map $\mathsf{Con}$ will have
$\operatorname{Fix}_{j}(\mathsf{Con})\leq a+j\cdot\ell$ (for relevant values
of $j$). This implies that:

######  Theorem 1.12 (informal).

It is unlikely that a random construction map (which is an extractor w.h.p)
will have a “useful” reduction with $q<2^{\ell}$.

More details, and a precise statement is given in Section 3.1.2. This
demonstrates that requiring a construction to have $q<2^{\ell}$ and be useful
for PRGs (and not just for extractors) places limitations on the structure of
the construction.

##### Our interpretation.

Our interpretation of Theorem 1.11 is that in order to enable the reduction to
make few queries, the construction must “create a backdoor” and introduce
correlations between different outputs. These correlations are “slightly
harmful” to the goal of being an extractor. More precisely, having low
$\operatorname{Fix}_{j}(\mathsf{Con})$ means that there is a source
distribution with min-entropy that is very high (only lacking
$\operatorname{Fix}_{j}(\mathsf{Con})$ bits of information) on which $j$
outputs of the extractor are fixed. This will violate the extractor guarantee
if $j$ is close to $2^{r}$ (but is possible for $j\ll 2^{r}$ which is the case
in Theorem 1.11).

Theorems 1.11 and 1.12 suggest that it is more difficult to design PRG
constructions than extractors. In Section 3.1.3 we review the known
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ constructions
in the literature (the Nisan-Wigderson PRG [NW94] and the Shaltiel-Umans PRG
[SU05, Uma03]) observing how they achieve low
$\operatorname{Fix}_{j}(\mathsf{Con})$ in the high-end, and why they do not
achieve this in the extreme high-end. We hope that understanding conditions
that $\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$
constructions must satisfy, may point us to new constructions that may be
applicable in the extreme high-end.

##### Technique.

We consider a “distinguisher” $D_{f}:\\{0,1\\}^{m}\to\\{0,1\\}$ that answers
one iff its input is an output of $\mathsf{Con}_{f}$. For every function
$f\in\mathcal{F}_{\ell,1}$, as $D_{f}$ $\mathsf{PRG}\mbox{-}\mathsf{breaks}$
$\mathsf{Con}_{f}$, by Definition 1.7, there must exist
$\alpha\in\\{0,1\\}^{a}$ such that the function
$C(x)=\mathsf{Red}^{D_{f}}(x,\alpha)$ satisfies $C=f$. However, $D_{f}$ only
answers one on $2^{r}$ out of the possible $2^{m}$ queries. If $\mathsf{Red}$
does not ask such “interesting queries”, then it obtains no information on
$f$, and cannot hope to reconstruct every $f\in\mathcal{F}_{\ell,1}$.

How does $\mathsf{Red}$ know to ask interesting queries? The advice string
$\alpha$ (that depends on $f$) may give $\mathsf{Red}$ information about
interesting queries. However, the information in the advice string is limited
by its length $a$, and we show that if $\mathsf{Red}$ is able to find
interesting queries for many choices of $f\in\mathcal{F}_{\ell,1}$ and
$x\in\\{0,1\\}^{\ell}$, then after this “fixed cost” of $a$ bits of
information, it is still difficult for $\mathsf{Red}$ to find interesting
queries, unless the construction $\mathsf{Con}$ is set up so that many
interesting queries (that is, outputs of $\mathsf{Con}_{f}$) have low
information, giving that $\operatorname{Fix}_{j}(\mathsf{Con})\leq
a+j\cdot(\log q+O(1))$ for many values of $j$). The precise details are given
in Section 3.

####  1.3.2 Limitations on the “PEG + Extractor” approach of [DMOZ20]

Doron et al. [DMOZ20] showed how to construct extreme high end PRGs from a
strengthening of the extreme high-end hardness assumption of Open Problem 1.5.
More specifically, rather than only assuming that $f$ cannot be computed by
circuits of size $2^{(1-o(1))\cdot\ell}$, it is assumed that this holds even
for circuits that are allowed to use nondeterminism and randomness (and can be
thought of as a nonuniform analog of the class MA). This assumption is
significantly stronger then the extreme high-end hardness assumption
(although, still plausible).

##### The PEG + extractor approach.

The approach of [DMOZ20] is to construct a pseudo-entropy generator (PEGs)
(for a specific notion of “computational entropy” suggested in [BSW03]). This
type of PEG can be thought of as a weak notion of PRGs, that is only
guaranteed to fool tests that accept a very small fraction of the $2^{m}$
inputs:

######  Definition 1.13 (PEGs).

A function $G:\\{0,1\\}^{r}\to\\{0,1\\}^{m}$ is a $(k,\epsilon)$-PEG for a
function $D:\\{0,1\\}^{m}\rightarrow\\{0,1\\}$, if $\Pr[D(U_{m})=1]\leq
2^{k-m}$ then $\Pr[D(G(U_{r}))=1]-\Pr[D(U_{m})=1]\leq\epsilon$. We say that
$D$ $(k,\epsilon)$-$\mathsf{PEG}\mbox{-}\mathsf{breaks}$ $G$, if $G$ is not an
$\epsilon$-PEG for $D$.101010We remark that the requirement that
$\Pr[D(G(U_{r}))=1]-\Pr[D(U_{m})=1]\leq\epsilon$ is sometimes replaced by the
stronger requirement that $\Pr[D(G(U_{r}))=1]\leq\epsilon$, or following
[BSW03], by the requirement that $\Pr[D(G(U_{r}))=1]\leq\Pr[D(U_{m})=1]\cdot
2^{m-k}+\epsilon$ which is stronger still, if we replace $\epsilon$ by
$\epsilon^{\prime}=\epsilon/2$ and $k$ by
$k^{\prime}=k+\log(1/\epsilon^{\prime})$. We are interested in proving
limitations on PEG and so taking a weak definition only makes our results
stronger (especially as we are interested in constant $\epsilon$ and $k\ll m$
and the distinction between $k,\epsilon$ and $k^{\prime},\epsilon^{\prime}$ is
immaterial).

More specifically, when given a function
$f:\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}$ (which is hard against the stronger
model of circuits equipped with nondeterminism and randomness) the
construction of [DMOZ20] works in two steps:

  1. 1.

PEG: Use the hard function to construct a PEG
$\operatorname{PEG}:\\{0,1\\}^{r_{\operatorname{PEG}}=o(\ell)}\to\\{0,1\\}^{m_{\operatorname{PEG}}=2^{(1-o(1))\cdot\ell}}$
for $k_{\operatorname{PEG}}=2^{(1-o(1))\cdot\ell}$.

  2. 2.

Extractor: Use an explicit extractor
$\operatorname{EXT}:\\{0,1\\}^{m_{\operatorname{PEG}}}\times\\{0,1\\}^{r_{\operatorname{EXT}}=(1+o(1))\cdot\ell}\to\\{0,1\\}^{m=2^{(1-o(1))\cdot\ell}}$
with entropy threshold $k_{\operatorname{PEG}}$ (such explicit constructions
are known unconditionally).

The final PRG
$G:\\{0,1\\}^{r=r_{\operatorname{PEG}}+r_{\operatorname{EXT}}}\rightarrow\\{0,1\\}^{m}$
is obtained by interpreting a string $y\in\\{0,1\\}^{r}$ as two strings
$y_{1}\in\\{0,1\\}^{r_{\operatorname{PEG}}}$ and
$y_{2}\in\\{0,1\\}^{r_{\operatorname{EXT}}}$, and setting
$G(y)=\operatorname{EXT}(\operatorname{PEG}(y_{1}),y_{2})$.

##### The seed length of a PEG.

The final seed length of $G$ is
$r=r_{\operatorname{PEG}}+r_{\operatorname{EXT}}$. Using lower bounds on the
seed length of extractors [RTS00], it follow that
$r_{\operatorname{EXT}}\geq\log(m_{\operatorname{PEG}}-k_{\operatorname{PEG}})\geq(1-o(1))\cdot\ell$.
Therefore, in order to achieve $r=(1+o(1))\cdot\ell$ (as is the case in the
extreme high-end) it is crucial to use a PEG with seed length
$r_{\operatorname{PEG}}=o(\ell)$. (We note that unlike PRGs, PEGs can
potentially achieve $r=o(\log m)$, whereas, as noted earlier, PRGs must have
$r\geq\log m-O(\log\log m)$).

Summing up, the construction of Doron et al. [DMOZ20] relies on the
observation that PEGs are weaker objects than PRGs (and are therefore easier
to construct) and that PEGs may have seed length that is significantly shorter
than PRGs, so that summing the two seed lengths can still yield an almost
optimal seed length.

##### Impossibility for black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PEG}$ proofs.

We show an obstacle on this approach when starting from the extreme high-end
assumption of Open Problem 1.5. More specifically, we show that black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PEG}$ proofs with
$r<\ell-\log(\ell)$ that make $q\leq 2^{\ell}$ queries, do not exist.

This means that the seed length of each of the two steps must be roughly
$\ell$ and so the total seed length of a PEG + extractor must be at least

$r_{\operatorname{PRG}}=r_{\operatorname{PEG}}+r_{\operatorname{EXT}}\geq(\ell-o(1))+(\ell-o(1))=2\ell-o(1)>(2-o(1))\cdot\log
m,$

showing an obstacle for achieving extreme high-end PRGs with this approach.
This is stated formally in the next theorem.

######  Theorem 1.14 (Impossibility of black-box PEGs with $r<\log m$).

There exists a constant $\nu>0$ such that for every black-box
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow({k},{\epsilon})\mbox{-}\mathsf{PEG}$
proof $(\mathsf{Con},\mathsf{Red})$ with parameters $\ell,r<k,m,a\leq\nu\cdot
2^{\ell},\epsilon\leq 1-2^{r-m},\rho\geq 0.51$ such that $\mathsf{Red}$ makes
$q\leq 2^{\ell}$ queries, it follows that:111111We have not yet formally
defined the notion of
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow({k},{\epsilon})\mbox{-}\mathsf{PEG}$
proof. However, this definition is obtained by simply replacing “PRG-break”
with “PEG-break” in Definition 1.7. For completeness, we give the full
definition in Section 3.2.

$r\geq\ell-\log\ell-O(1).$

Summing up, Theorem 1.14 shows that black-box proofs cannot be used to solve
Open Problem 1.5 using the PEG + extractor approach of Doron et al.
[DMOZ20].121212In light of Theorem 1.14 one may ask how Doron et al. [DMOZ20]
construct their PEG. Is their proof non-black-box? The answer is that their
proof is black-box, but it allows the reduction $\mathsf{Red}$ to use
nondeterminism and randomness (and it is this ability that enables the
reduction to make few queries). The cost of using these resources is that the
reduction only contradicts the hardness of $f$ if it is assumed to be hard
even for circuits equipped with these resources. See e.g., Applebaum et al.
[AASY16] for a discussion on nondeterministic reductions.

##### Consequences of Theorem 1.14 for “quantified derandomization”.

The notion of PEGs in Definition 1.13 is closely related to “quantified
derandomization” (introduced by Goldreich and Wigderson [GW14], see survey
article by Tell [Tel21]). Quantified derandomization is concerned with
derandomizing algorithms that err on very few (say less than $2^{k}$) of the
possible $2^{m}$ values of their $m$ random bits. This means that PEGs are
exactly the type of PRGs that are suitable for this derandomization (see
[DMOZ20, Tel21] for a discussion).

Consequently, Theorem 1.14 can also be viewed as a limitation on black-box
proofs that obtain PRGs with very short seed for quantified derandomization,
starting from the extreme high-end hardness assumption.

##### Technique.

Theorem 1.14 follows from Theorem 1.11 (noting that Theorem 1.11 also applies
to PEGs). Loosely speaking, if $r$ is small, then the number of outputs of
$\mathsf{Con}$ is small, and it is impossible for
$\operatorname{Fix}_{j}(\mathsf{Con})$ to be small for large values of $j$,
ruling out black-box proofs in which $r$ is small.

####  1.3.3 Lower bounds on black-box hardness amplification at the extreme
high-end

Grinberg, Shaltiel and Viola [GSV18] (continuing a line of previous work
[Vio06, SV10, AS14]) proved a lower bound of
$q\geq\Omega(\frac{\ell}{\epsilon^{2}})$ on the number of queries in
reductions for black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{(\frac{1}{2}+\epsilon)}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$
proofs (a.k.a. hardness amplification). By Proposition 1.8, such bounds imply
that using black-box proofs to convert a function $f$ on $\ell$ bits, that
cannot be computed by size $s$ into one that is average case hard for circuits
of size $m$, one must have $m\leq\frac{s-a}{q}\leq\frac{s}{q}$ which means
that such transformation “lose a factor $q$ in the hardness”.

In this paper we prove a lower bound of $q\geq\Omega(\frac{1}{\epsilon})$,
which is quantitatively weaker than that of [GSV18], but unlike [GSV18] it
applies in the extreme high-end. That is, our result allows
$a=2^{(1-o(1))\cdot\ell}$ whereas [GSV18] (as well as all previous bounds)
only works if $a\leq 2^{\nu\cdot\ell}$ for some constant $\nu>0$. (It is open
to match the bound of [GSV18] for large $a$).

######  Theorem 1.15 (Lower bounds on black-box hardness amplification at the
extreme high-end).

Let $(\mathsf{Con},\mathsf{Red})$ be a
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{(\frac{1}{2}+\epsilon)}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$
proof with parameters
$\ell,\ell^{\prime},a,\rho=1,\rho^{\prime}=\frac{1}{2}+\epsilon$. If
$\epsilon\leq\frac{1}{10}$, $\ell^{\prime}\geq\log(1/\epsilon)+\Omega(1)$ and
$a\leq\frac{2^{\ell}}{10}$ then $\mathsf{Red}$ must make at least $q$ queries
for

$q\geq\max\left(\Omega\left(\frac{1}{\epsilon}\right),\Omega\left(\ell-\log(2a)\right)\right).$

To the best of our knowledge, Theorem 1.15 is the first bound on the number of
queries in black-box hardness amplification that applies for $a\geq
2^{\ell/2}$ and to the extreme high-end.

Using Proposition 1.8, Theorem 1.15 implies that even if one starts from the
extreme high-end hardness assumption, then to obtain a
${(\frac{1}{2}+\frac{1}{m})}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$
for circuits of size $m$ (and apply the hybrid argument as explained in
Section 1.2.4) there must be a “hardness loss”, and
$m\leq\frac{2^{\ell}}{q}\leq\frac{2^{\ell}}{m}$, implying that $m\leq
2^{\ell/2}$.

Note that this limitation applies regardless of the length $\ell^{\prime}$ of
the input length of $\mathsf{Con}_{f}$. This means that a black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proof that
relies on hardness amplification and the hybrid argument (that is:
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{(\frac{1}{2}+\frac{1}{m})}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$)
must have $m\leq 2^{\ell/2}$, and this holds even if the seed length $r$ of
the PRG is large.

In the next section we show that a similar argument also gives limitations on
using hardness amplification together with the “PRG composition” approach of
Chen and Tell [CT21b].

##### Technique.

The work of [GSV18] (as well as previous work in this area) relied on
information theoretic techniques that break down for large $a$. Indeed, the
proof of Theorem 1.15 uses a different argument. This argument builds on ideas
of Applebaum et al. [AASY16] which connect the number of queries required by a
reduction (or in the case of [RSV21] a local list-decoding algorithm) to the
success that small size, constant depth circuits have in solving the “coin
problem” (that is distinguishing a sequence of independent tosses of an
unbiased coin from a sequence of independent tosses of a slightly biased
coin). The proofs of [AASY16, RSV21] do not work for $a\geq 2^{\ell/2}$ and
our results are obtained by proving tighter bounds on depth 3 circuits for
specific versions of the coin problem that come up in the argument. The proof
is given in Section 4. As a consequence, we also improve the bounds of [RSV21]
on the number of queries of local list-decoding algorithms, see Section 5 for
details.

####  1.3.4 The hybrid argument and the “PRG composition” approach of [CT21b]

Chen and Tell [CT21b] construct extreme high end PRGs if, in addition to the
extreme high-end hardness assumption of Open Problem 1.5, one also assumes the
existence of one-way functions (OWFs). The existence of OWFs is a standard and
widely believed assumption in cryptography. Nevertheless, OWFs (or more
generally cryptography) are not known to be implied by extreme high-end PRGs
(or other PRGs in complexity theory). Assuming OWFs does not seem necessary.

##### The PRG composition approach.

Chen and Tell [CT21b] start from a hard function
$f:\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}$ given by the extreme high-end
hardness assumption. Their PRG
$G:\\{0,1\\}^{(1+o(1))\cdot\ell}\to\\{0,1\\}^{2^{(1-o(1))\cdot\ell}}$ is
obtained by PRG composition, namely $G(y)=G_{2}(G_{1}(y))$ where:

  1. 1.

$G_{1}:\\{0,1\\}^{(1+o(1))\cdot\ell}\to\\{0,1\\}^{m_{1}=2^{\Omega(\ell)}}$ is
a PRG against circuits of size $2^{(1-o(1))\cdot\ell}$ that is constructed
from the extreme high-end hardness assumption using hardness amplification,
the Nisan-Wigderson PRG, and the hybrid argument.131313More precisely, the
cost of the hybrid argument (explained in Section 1.2.4) is measured in terms
of the output length $m$ (even if the PRG fools circuits of larger size, as is
the case here). This means, that the goal of fooling circuits of size
$2^{(1-o(1))\cdot\ell}$ can be achieved by known black-box proofs (in the same
manner explained in Section 1.2.4) from the extreme high-end hardness
assumption for PRGs that output $m_{1}=2^{\Omega(\ell)}$ bits, rather than
$m=2^{(1-o(1))\cdot\ell}$ bits.

  2. 2.

$G_{2}:\\{0,1\\}^{m_{1}=2^{\Omega(\ell)}}\to\\{0,1\\}^{m=2^{(1-o(1))\cdot\ell}}$
is a PRG with modest stretch (polynomial rather than exponential) that
suffices to push the output length from $m_{1}=2^{\Omega(\ell)}$ to
$m=2^{(1-o(1))\cdot\ell}$. Nevertheless, for the composition to be a PRG, it
is crucial that $G_{2}$ can be computed in time $2^{(1-o(1))\cdot\ell}$ (that
is in almost linear time in its output length $m$).141414This requirement is
necessary as in the composition one needs to consider a distinguisher for
$G_{1}$ that runs $G_{2}$ as a procedure, and $G_{1}$ cannot fool circuits of
size larger than $2^{\ell}$. We also remark that in contrast to cryptography,
in hardness vs. randomness, efficiency of components is rarely used in proving
security of the final primitive, and this is one such rare instance. Such PRGs
indeed follow from the existence of OWFs [HILL99].

A natural question is whether it is possible to construct the PRG $G_{2}$ from
the extreme high-end hardness assumption. This will remove the need for OWFs.

PRGs with polynomial stretch follow from this assumption (and even from weaker
versions like the high-end hardness assumption or “low-end” versions). This is
good news, as it shows that hardness amplification and the hybrid argument
_can_ yield sufficient stretch in this case.

The issue is that the PRGs constructed by these methods do not run in time
that is nearly linear in their output length $m$ (and instead run in time
$m^{c}$ where $c>2$). This means that they are unsuitable for the PRG
composition approach (and this is why [CT21b] relies on OWFs).

##### Our results.

Theorem 1.15 implies that PRGs (even with modest stretch) cannot run in nearly
linear time, if they are obtained using black-box hardness amplification and
the hybrid argument, assuming the extreme high-end hardness assumption. This
implies that if we only assume the extreme high-end hardness assumption (and
do not assume the existence of OWFs) then current techniques cannot yield the
PRG $G_{2}$ required by the PRG composition.

More precisely, we have already seen in Section 1.3.3 that in order to do a
hybrid argument for output length $m$, one needs a hardness amplification
result that amplifies to below $\frac{1}{2}+\frac{1}{m}$, and that Theorem
1.15 implies that $m\leq 2^{\frac{\ell}{2}}$. This holds in the extreme high-
end, regardless of the relationship between $r$ and $m$. In particular, it
also holds when trying to construct PRGs with modest stretch like $G_{2}$,
assuming the extreme high-end hardness assumption. On the other hand, assuming
that computing the average-case hard function $\mathsf{Con}_{f}$ takes at
least the time it takes to compute the worst-case hard function $f$, and
recalling that $f$ cannot be computed by circuits of size
$2^{(1-o(1))\cdot\ell}$, we conclude that $\mathsf{Con}_{f}$ cannot be
computed in time $2^{(1-o(1))\cdot\ell}$ (which is at least $m^{2-o(1)}$).

Summing up, after performing hardness amplification, there must be at least a
quadratic gap between the time it takes to compute $\mathsf{Con}_{f}$, and the
circuit size for which it is hard on average. This gap is inherited by the
final PRG $G_{2}$. Consequently, $G_{2}$ cannot run in time smaller than
$m^{2-o(1)}$, and in particular, there is in obstacle for obtaining PRGs that
run in time nearly linear in $m$, using these techniques (even if the stretch
is modest).

This shows an obstacle for using current techniques (that rely on hardness
amplification and the hybrid argument) to apply the PRG composition approach
of [CT21b] assuming only the extreme high-end hardness assumption. This
partially explains why [CT21b] need the additional assumption that OWFs exist
in order to construct the PRG $G_{2}$.

###  1.4 Organization of this paper

In Section 2 we define some notation, and cite some previous work that we use.
In Section 3 we prove our results on black-box proofs for PRGs and PEGs
(Theorem 1.11 and Theorem 1.14). In Section 4 we prove our results on hardness
amplification (Theorem 1.15). In Section 5 we use the methodology devised for
Theorem 1.15 to improve the lower bounds of Ron-Zewi, Shaltiel and Varma
[RSV21] on the number of queries of decoders for locally decodable codes. In
Section 6 we mention some open problems.

##  2 Preliminaries

##### Distributions and Random Variables.

We use $X\leftarrow D$ to denote the experiment in which $X$ is chosen from
distribution $D$. For a set $A$ we use $X\leftarrow A$ to denote the
experiment in which $X$ is chosen uniformly from $A$. Two distributions $X,Y$
over the same finite domain are $\epsilon$-close if for every event $A$,
$|\Pr[X\in A]-\Pr[Y\in A]|\leq\epsilon$. For a distribution $X$ over
$\\{0,1\\}^{n}$, we define
$H_{\infty}(X)=\min_{x\in\\{0,1\\}^{n}}\log\frac{1}{\Pr[X=x]}$.

For $0\leq p\leq 1$, we use $U^{p}_{n}$ to denote the distribution of $n$
i.i.d. random variables, where each one has probability $p$ to be one. We use
$U_{n}$ to denote $U^{1/2}_{n}$ (the uniform distributions on $n$ bit
strings).

##### Hamming distance and weight.

For two strings $x,y\in\\{0,1\\}^{n}$ we use $\mathsf{dist}(x,y)$ to denote
the relative Hamming distance between $x$ and $y$, namely,
$\mathsf{dist}(x,y)=|\left\\{{i\in[n]:x_{i}\neq y_{i}}\right\\}|/n$. We use
$\operatorname{weight}(x)$ to denote the absolute Hamming weight, namely
$\operatorname{weight}(x)=|\left\\{{i\in[n]:x_{i}\neq y_{i}}\right\\}|$.

##### Restrictions.

We use the standard notion of random restrictions. Namely, a restriction
$\rho:[n]\to\left\\{{0,1,*}\right\\}$ restricts some of the variables of a
function $f:\\{0,1\\}^{n}\to\\{0,1\\}$.

We use $\operatorname{Select}(\rho)$ to denote the subset of free variables,
$\operatorname{Free}(\rho)$ to denote the number of free variables, and
$\operatorname{Assign}(\rho)$ to be the value of the assigned variables. This
is stated formally in the next definition.

######  Definition 2.1 (Restrictions).

A restriction of $n$ variables is a function
$\rho:[n]\to\left\\{{0,1,*}\right\\}$. We define
$\operatorname{Select}(\rho)=\left\\{{i:\rho(i)=*}\right\\}$,
$\operatorname{Free}(\rho)=|\operatorname{Select}(\rho)|$, and
$\operatorname{Assign}(\rho)\in\\{0,1\\}^{n-\operatorname{Free}(\rho)}$ by
enumerating the fixed elements
$(i_{1}<\ldots<i_{n-\operatorname{Free}(\rho)})=[n]\setminus\operatorname{Select}(\rho)$
and defining $\operatorname{Assign}(\rho)_{j}=\rho(i_{j})$.

Given a function $f:\\{0,1\\}^{n}\to\\{0,1\\}$ and a restriction
$\rho:[n]\to\left\\{{0,1,*}\right\\}$, and
$x\in\\{0,1\\}^{\operatorname{Free}(\rho)}$ we define
$\operatorname{Fill}_{\rho}(x)\in\\{0,1\\}^{n}$ as follows: Let
$i_{1}<\ldots<i_{\operatorname{Free}(\rho)}$ be the indices on which $\rho$
outputs ‘$*$’,

$\operatorname{Fill}_{\rho}(x)_{i}=\left\\{\begin{array}[]{ll}x_{j},&\exists
j\mbox{ s.t.\ }i=i_{j}\\\ \rho(i),&\mbox{otherwise}\end{array}\right.$

Given $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, we define
$f_{\rho}:\\{0,1\\}^{\operatorname{Free}(\rho)}\to\\{0,1\\}$ by

$f_{\rho}(x)=f(\operatorname{Fill}_{\rho}(x)).$

We use $\mathsf{R}^{n}_{p}$ to denote the set of restrictions with $p\cdot n$
unrestricted variables. A formal definition is given below.

######  Definition 2.2 (The class $\mathsf{R}^{n}_{p}$).

For $0\leq p\leq 1$, let $\mathsf{R}^{n}_{p}$ denote the set of restrictions
$\rho:[n]\to\left\\{{0,1,*}\right\\}$ with $\operatorname{Free}(\rho)=p\cdot
n$.

We use the following switching lemma due to Hastad [Hås86]. The specific
version used here, appears in Beame’s primer [Bea94].

######  Theorem 2.3.

[Hås86, Bea94] Let $C$ be a $q$-CNF over $n$ variables. For every $0\leq p\leq
1$, the probability over choosing $\rho\leftarrow\mathsf{R}^{n}_{p}$ that
$C_{\rho}$ does not have a decision tree of height $h$ is at most $(7\cdot
p\cdot q)^{h}$.

##  3 Limitations on black-box proofs for PRGs and PEGs

In this section we discuss our main results on black-box proofs for PRGs and
PEGs (Theorem 1.11 and Theorem 1.14). In Section 3.1 we discuss Theorem 1.11,
and in Section 3.2 we discuss Theorem 1.14. The proofs of both these Theorems
is given in Section 3.3.

###  3.1 Limitations on constructions of black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proofs

In this section we restate Theorem 1.11 and discuss its consequences and
interpretation. In Section 3.1.1 we restate Theorem 1.11 and discuss its
interpretation. In Section 3.1.2 we show that a corollary of Theorem 1.11 is
that PRG constructions must differ from typical extractor constructions,
giving a precise statement of Theorem 1.12. In Section 3.1.3 revisit the
Nisan-Wigderson PRG [NW94] and the Shaltiel-Umans PRG [SU05, Uma03] and
discuss them from the perspective of Theorem 1.11.

####  3.1.1 A general statement of Theorem 1.11

##### Review of the setup of Theorem 1.11.

Theorem 1.11 shows that for any black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proof
$(\mathsf{Con},\mathsf{Red})$, if $\mathsf{Red}$ is useful, and makes $q\leq
2^{\ell}$ queries, then $\mathsf{Con}$ must be structured in a way that allows
“fixing many outputs, with small information cost”. This is measured by
$\operatorname{Fix}_{j}(\mathsf{Con})$ from Definition 1.10, which defines
$\operatorname{Fix}_{j}(\mathsf{Con})$ to be the minimal number $h$, so that
when $F$ is chosen at random from $\mathcal{F}_{\ell,1}$, it is possible to
fix $j$ outputs of $\mathsf{Con}_{F}$, while only reducing $h$ bits of
information about $F$.

Theorem 1.11 shows that in order for $\mathsf{Red}$ to be useful and have
$q\leq 2^{\ell}$, it must be that for many sufficiently large choices of $j$,
$\operatorname{Fix}_{j}(\mathsf{Con})\leq a+j\cdot(\log q+O(1))$. This means
that after a “fixed cost” of $a$ bits of information, a large number of
outputs of $\mathsf{Con}_{F}$ can be fixed at the cost of $\log q+O(1)$ bits
of information about $F$, per output.

##### A more general statement.

The following theorem is a generalized version of Theorem 1.11 which also
allows the parameter $\rho$ (measuring how hard on average is the function we
start from) to be very close to $\frac{1}{2}$, and then the amortized cost
$\log q+O(1)$, is replaced by $\log\frac{q}{\rho-\frac{1}{2}}$.

######  Theorem 3.1.

Let $(\mathsf{Con},\mathsf{Red})$ be a black-box
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\epsilon}\mbox{-}\mathsf{PRG}$
proof for parameters $\ell,r,m,a,\epsilon,\rho$ such that $\mathsf{Red}$ makes
at most $q\leq 2^{\ell}$ queries. If $\rho=\frac{1}{2}+\eta$, $\eta\geq
2^{-\ell}$, $\epsilon\leq 1-2^{r-m}$, and $a\leq\nu\cdot\eta^{2}\cdot
2^{\ell}$ for some sufficiently small constant $\nu>0$, then for
$j_{\max}=\nu\cdot\frac{\eta^{2}\cdot 2^{\ell}}{\ell}$, and every $j\leq
j_{\max}$,

$\operatorname{Fix}_{j}(\mathsf{Con})\leq a+j\cdot(\log
q+\log\frac{4}{\eta}).$

Theorem 1.11 immediately follows from Theorem 3.1 by setting $\rho=0.51$.
Theorem 3.1 is proven in Section 3.3.

##### A discussion of the parameters of Theorem 3.1.

The parameters in Theorems 1.11 and Theorem 3.1 are applicable even for very
large $a$, and therefore Theorem 3.1 applies in the extreme high-end (where
$a=2^{(1-o(1))\cdot\ell}$) as well as in less challenging ranges such as the
high-end (where $a=2^{\nu\cdot\ell}$ for a constant $\nu>0$) and the low-end
(where $a=\operatorname{poly}(\ell)$). We stress that to the best of our
knowledge, previous limitations on the number of queries of a black-box
reduction (of any kind) did not apply for $a\geq 2^{\ell/2}$ and in
particular, for the extreme high-end. See Section 4 for a discussion on past
lower bounds on the number of queries by reductions for black-box hardness
amplification proofs.

Furthermore, Theorems 1.11 and Theorem 3.1 make no assumption on the stretch
(namely, the relationship between $r$ and $m$) of the constructed PRG, and
apply even when the stretch is very small, and $m$ is only slightly larger
than $r$. In addition, the theorem applies even when $\epsilon$ is very large,
and approaches one (rather than zero).

Finally, Theorem 3.1 applies even when $\eta=\frac{1}{2}-\rho$ is very small
(say $\eta=2^{-\Omega(\ell)})$ and even for black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proofs like
the Nisan-Wigderson PRG, which are only known to work when $\eta$ is very
small. See Section 3.1.3 for a discussion of the Nisan-Wigderson PRG.

####  3.1.2 black-box PRGs are different than typical extractors

In this section we prove Theorem 1.12 which loosely states that a random
construction $\mathsf{Con}$ for a black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proof is
likely to be an extractor, but unlikely to be useful when transforming hard
functions into PRGs.

##### Formal connection between extractors and black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proofs.

It is well known following Trevisan’s breakthrough construction [Tre01] (and
as explained in Section 1.2.3) that black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proofs, are
closely related to randomness extractors. Let us formally specify this
connection. We start with a formal definition of randomness extractors.

######  Definition 3.2 (extractors).

A function $E:\\{0,1\\}^{n}\times\\{0,1\\}^{r}\to\\{0,1\\}^{m}$ is a
$(k,\epsilon)$-extractor if for every distribution $X$ over $\\{0,1\\}^{n}$,
with $H_{\infty}(X)\geq k$, $E(X,U_{r})$ is $\epsilon$-close to $U_{m}$.

In order to compare function
$E:\\{0,1\\}^{n}\times\\{0,1\\}^{r}\to\\{0,1\\}^{m}$ to functions
$\mathsf{Con}:\mathcal{F}_{\ell,1}\to\mathcal{F}_{r,m}$ we use the following
notation.

######  Definition 3.3 (Constructions and extractors).

A string $f\in\\{0,1\\}^{n}$ can be viewed as a function $f:\\{0,1\\}^{\log
n}\to\\{0,1\\}$ by $f(i)=f_{i}$. This also applies in the other direction,
allowing a function $f:\\{0,1\\}^{\ell}\to\\{0,1\\}$ to be viewed as a string
$f\in\\{0,1\\}^{2^{\ell}}$.

Given a function $E:\\{0,1\\}^{n}\times\\{0,1\\}^{r}\to\\{0,1\\}^{m}$, we
define $\ell=\log n$, and
$\mathsf{Con}^{E}:\mathcal{F}_{\ell,1}\to\mathcal{F}_{r,m}$ where
$\mathsf{Con}^{E}_{f}:\\{0,1\\}^{r}\to\\{0,1\\}^{m}$ is defined by
$\mathsf{Con}^{E}_{f}(y)=E(f,y)$. This also applies in the other direction,
where a function $\mathsf{Con}:\mathcal{F}_{\ell,1}\to\mathcal{F}_{r,m}$
induces a function
$E:\\{0,1\\}^{n=2^{\ell}}\times\\{0,1\\}^{r}\to\\{0,1\\}^{m}$ by
$E(f,y)=\mathsf{Con}_{f}(y)$.

With this notation, extractors and black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proofs, are
essentially equivalent. This is stated in the following standard proposition
which shows that the two notions are roughly equivalent for $a\approx k$.

######  Proposition 3.4 (Extractors are essentially equivalent to black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proofs).

Let $E:\\{0,1\\}^{n}\times\\{0,1\\}^{r}\to\\{0,1\\}^{m}$, and let $\ell=\log
n$.

  1. 1.

If $\mathsf{Con}^{E}$ can be matched with an oracle procedure
$\mathsf{Red}^{(\cdot)}$ such that the pair $(\mathsf{Con}^{E},\mathsf{Red})$
is a black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\epsilon}\mbox{-}\mathsf{PRG}$
proof with advice length $a$, then $E$ is a $(k,2\epsilon)$-extractor, for
$k=a+\log(1/\epsilon)+1$.

  2. 2.

If $E$ is a $(k,\epsilon)$-extractor then there exists an oracle procedure
$\mathsf{Red}^{(\cdot)}$ such that the pair $(\mathsf{Con}^{E},\mathsf{Red})$
is a black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\epsilon}\mbox{-}\mathsf{PRG}$
proof with advice length $a=k+1$.

##### Reductions must make few queries to be useful.

Note however, that in order to be useful for PRG construction, a black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proof must
have a reduction $\mathsf{Red}$ that make few queries. In particular, as can
be seen in Proposition 1.8, the reduction is useless if it makes $q\geq
2^{\ell}$ queries (and even if it makes $q\geq\frac{2^{\ell}-a}{m}$ queries).

The equivalence of Proposition 3.4 does not mention the number of queries
(which can be as large as $2^{m}$). In other words, a black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proof is an
extractor even when the number of queries is very large, but it must have
$q\ll 2^{\ell}$ in order to be useful when converting hard functions into
PRGs.

##### A typical extractor is not a useful PRG construction.

We now show that for a wide range of parameters $\ell,r,m$ and $a$ (and in
particular for the parameters that correspond to the high-end and the extreme
high-end) if we choose a function
$E:\\{0,1\\}^{n}\times\\{0,1\\}^{r}\to\\{0,1\\}^{m}$ uniformly at random then:

  * •

It is unlikely that construction $\mathsf{Con}^{E}$ (associated with $E$) has
small $\operatorname{Fix}_{j}(\mathsf{Con}^{E})$, and therefore, by Theorem
1.11, it is unlikely that $\mathsf{Con}^{E}$ can be matched with a reduction
$\mathsf{Red}$ that makes $q\leq 2^{\ell}$ queries.

  * •

However, a standard argument shows that it is likely that $E$ is an extractor,
and therefore, by Proposition 3.4, it is likely that $\mathsf{Con}^{E}$ can be
matched with a reduction $\mathsf{Red}$ (although $\mathsf{Red}$ may make
$q=2^{m}$ queries).

As explained in Section 1.3.1, this can be interpreted as saying that PRG
constructions must be quite different than typical extractor constructions in
order to allow the existence of a reduction that makes few queries.

A formal and quantitative version of this is stated in the next definition and
theorem.

######  Definition 3.5 (Random construction).

Let $E\leftarrow\mathsf{RndE}_{\ell,r,m}$ denote the experiment in which a
function $E:\\{0,1\\}^{n=2^{\ell}}\times\\{0,1\\}^{r}\to\\{0,1\\}^{m}$ is
chosen uniformly from the set of all such functions.

######  Theorem 3.6.

Let $\ell,r,m,a,\epsilon$ be parameters such that $m\geq 2r$ and the following
holds:

Parameters that allow $E$ to be an extractor:
$r\geq\ell+2\log(1/\epsilon)+O(1)$, $2^{\ell}\geq a\geq
m+2\log(1/\epsilon)+O(1)$, and $\epsilon\leq\frac{1}{2}$.

Parameters that prevent fixing seeds: $a+j\cdot\ell\leq
min(j\cdot(m-r)-O(1),\frac{2^{\ell}}{2})$.

In the experiment $E\leftarrow\mathsf{RndE}_{\ell,r,m}$ the following items
hold:

  * •

For every $j>4$, the probability that
$\operatorname{Fix}_{j}(\mathsf{Con}^{E})\leq a+j\cdot\ell$ is smaller than
$2^{-2^{2^{\ell}/2}}$.

Consequently (by Theorem 1.11) the probability that $\mathsf{Con}^{E}$ can be
matched with an oracle procedure $\mathsf{Red}^{(\cdot)}$ that makes
$q<2^{\ell}$ queries, is smaller than $2^{-2^{2^{\ell}/2}}$.

  * •

The probability that $E$ is an $(a+O(1),\epsilon)$ extractor is larger than
$1-o(1)$. Consequently (by Proposition 3.4) the probability that
$\mathsf{Con}^{E}$ can be matched with an oracle procedure
$\mathsf{Red}^{(\cdot)}$ with advice length $a+O(1)$ is larger than $1-o(1)$.

##### The parameters in Theorem 3.6.

We stress that Theorem 3.6 applies for a wide range of parameters including
the extreme high-end, and the high-end. Furthermore, Theorem 3.6 does not
require that $m$ is much larger than $r$ and applies even when the stretch is
small. Furthermore, the probability in the first item is $2^{-2^{2^{\ell}/2}}$
which is quite small. We also note that the requirement that $a+j\cdot\ell$ is
small are very mild in the following sense:

  * •

For every $j$ it is obvious that $\operatorname{Fix}_{j}(\mathsf{Con})\leq
j\cdot m$, as the amount of information in $j$ outputs is at most $j\cdot m$.
We are only requiring that $a+j\cdot\ell\leq j\cdot(m-r)-O(1)$ which is quite
close to the obvious bound.

  * •

The total amount of information in $f$ is at most $2^{\ell}$. We are only
requiring that $a+j\cdot\ell\leq\frac{2^{\ell}}{2}$ which is quite close to
the obvious bound.

###### Proof.

(of Theorem 3.6) The second item is a standard calculation which can be found
for example in [RTS00]. Therefore, we will only prove the first item. Within
this proof, unless otherwise specified, all probabilities are regarding the
experiment $E\leftarrow\mathsf{RndE}_{\ell,r,m}$.

For a fixed set $S\subseteq\\{0,1\\}^{n}$ of size $K=2^{n-(a+j\cdot\ell)}$ and
a sequence $\bar{z}=(z_{1},\ldots,z_{j})$ of distinct elements in
$\\{0,1\\}^{m}$, let $A_{S,\bar{z}}$ denote the event that for every $f\in S$,
there exist $y_{1},\ldots,y_{j}\in\\{0,1\\}^{r}$ such that for all $i\in[j]$,
$E(f,y_{i})=z_{i}$. This definition is made so that:

$\Pr[\operatorname{Fix}_{j}(\mathsf{Con}^{E})\leq
a+j\cdot\ell]\leq{2^{n}\choose K}\cdot 2^{m\cdot j}\cdot\Pr[A_{S,\bar{z}}],$

where the latter expression is obtained by a union bound over all choices of
$S$ and $\bar{z}$. For every such $S$ and $\bar{z}$, and for every $f\in S$,
let $A_{S,\bar{z},f}$ denote the event that there exist
$y_{1},\ldots,y_{j}\in\\{0,1\\}^{r}$ such that for all $i\in[j]$,
$E(f,y_{i})=z_{i}$. For every $f\in S$, by a union bound over all choices of
$y_{1},\ldots,y_{j}\in\\{0,1\\}^{r}$,

$\Pr[A_{S,\bar{z},f}]\leq 2^{r\cdot j}\cdot 2^{-m\cdot j}.$

These events are independent for the $K$ different choices of $f\in S$, and
therefore, the probability of their conjunction is the product of their
individual probabilities.

$\Pr[A_{S,\bar{z}}]\leq\left(2^{r\cdot j}\cdot 2^{-m\cdot
j}\right)^{K}=2^{-j\cdot K\cdot(m-r)}.$

We conclude that:

$\displaystyle\Pr[\operatorname{Fix}_{j}(\mathsf{Con}^{E})\leq a+j\cdot\ell]$
$\displaystyle\leq{2^{n}\choose K}\cdot 2^{m\cdot j}\cdot 2^{-j\cdot
K\cdot(m-r)}$ $\displaystyle\leq\left(\frac{2^{n}\cdot e}{K}\right)^{K}\cdot
2^{m\cdot j}\cdot 2^{-j\cdot K\cdot(m-r)}$

Let $v=2^{2^{\ell}/2}$. In order to show that this probability is smaller than
$2^{-v}$ it is sufficient to show that:

  1. 1.

$\left(\frac{2^{n}\cdot e}{K}\right)^{K}\cdot 2^{-j\cdot K\cdot(m-r)}\leq
2^{-2v}$, and

  2. 2.

$2^{m\cdot j}\leq 2^{v}$.

These two conditions follow by the requirements of the theorem. More
specifically, the requirement that $a+j\cdot\ell\leq\frac{2^{\ell}}{2}$ gives
that $K\geq 2^{2^{\ell}/2}\geq v$. This gives that the first condition follows
if $a+j\cdot\ell\leq j\cdot(m-r)-O(1)$ which is one of the requirements of the
theorem.

The second condition follows because by our requirement
$j\leq\frac{2^{\ell}}{2}$ and $m\leq 2^{\ell}$. Therefore for sufficiently
large $\ell$, $m\cdot j\leq 2^{2^{\ell}/2}=v$, ∎

####  3.1.3 Revisiting the Nisan-Wigderson PRG and the Shaltiel-Umans PRG

As surveyed in Section 1.2.4 there are only two known constructions of black-
box $\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proofs in
the literature, where $\mathsf{Red}$ is useful and makes $q$ queries, for $q$
that can be significantly less than $2^{\ell}$. These are the Nisan-Wigderson
PRG [NW94] and an additional construction is due to Shaltiel and Umans [SU05]
and Umans [Uma03].

The former is more versatile, and has many additional applications, mainly
because its reduction requires less computational resources, and makes less
queries. The latter has advantages over the Nisan-Wigderson PRG as it allows
to achieve $r=O(\ell)$ even for small values of $a$ (like
$a=\operatorname{poly}(\ell)$, which corresponds to “low-end” PRGs).

Nevertheless, as explained in Section 1.2.4, both these approaches rely on
hardness amplification and the hybrid argument, preventing them from achieving
the extreme high-end.

Theorem 1.11 and 3.1 show that in _any_ black-box proof with $q\leq 2^{\ell}$,
_even one that does not rely on the hybrid argument_ ,
$\operatorname{Fix}_{j}(\mathsf{Con})$ must be small. Let us review how the
known PRGs achieve this.

##### The Nisan-Wigderson PRG.

The Nisan-Wigderson PRG is a black-box
${(\frac{1}{2}+\frac{\epsilon}{m})}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\epsilon}\mbox{-}\mathsf{PRG}$
proof $(\mathsf{Con}^{NW},\mathsf{Red}^{NW})$ with parameters
$\ell,r,m,a,\rho=\frac{1}{2}+\frac{\epsilon}{m}$ and $\epsilon$, such that
$\mathsf{Red}$ makes a _single_ query. This means that the Nisan-Wigderson PRG
is applicable in the extreme high-end, when starting from a
$(\frac{1}{2}+\frac{\epsilon}{m})\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$.
As explained in Section 1.3.3 current hardness amplification techniques are
not applicable for $m\geq 2^{\ell/2}$. This means that they cannot be used in
the extreme high-end, even if we are willing to allow large seed length $r$.

By Theorem 3.1, we have that:

$\operatorname{Fix}_{j}(\mathsf{Con}^{NW})\leq a+j\cdot(\log m+O(1)),$

for constant $\epsilon>0$, and many values of $m$ and $j$. Let us review how
$\mathsf{Con}^{NW}$ achieves this.

The construction $\mathsf{Con}^{NW}$ is defined using a “design”, namely a
collection $S_{1},\ldots,S_{m}\subseteq[r]$ such that for every $i\in[m]$,
$|S_{i}|=\ell$, and then for every $f\in\mathcal{F}_{\ell,1}$,
$\mathsf{Con}^{NW}_{f}:\\{0,1\\}^{r}\to\\{0,1\\}^{m}$ is defined by

$\mathsf{Con}^{NW}_{f}(x)=f(x|_{S_{1}}),\ldots,f(x|_{S_{m}}).$

Another version that is often considered is a “seed extending” version
$\overline{\mathsf{Con}}^{NW}_{f}(x)=x,\mathsf{Con}^{NW}_{f}(x)$ that outputs
$m+r$ bits. The analysis of [NW94] shows that the parameter $a$ is determined
by the sizes of pairwise intersections of sets in the design. More
specifically, using an improved analysis by Raz, Reingold and Vadhan [RRV02]
(for a condition called “weak design”) it follows that taking

$a=\sum_{i\in[m]}\sum_{i^{\prime}\neq i}2^{|S_{i^{\prime}}\cap S_{i}|}\leq
m\cdot 2^{\max_{i\neq i^{\prime}}|S_{i}\cap S_{i^{\prime}}|},$

suffices to obtain a reduction $\mathsf{Red}^{NW}$ which makes a _single_
query.

The weak design property can be used to show that for every $1\leq j\leq
2^{\ell}$,

$\operatorname{Fix}_{j}(\overline{\mathsf{Con}}^{NW})\leq a+j.$

Loosely speaking, this is because the NW proof shows that for every $i$, after
fixing $a$ bits of information about $f$, we have that for every value of
$x|_{[r]\setminus S_{i}}$, all $m-1$ output bits of the form
$f(x|_{S_{i^{\prime}}})$ for $i^{\prime}\neq i$ are completely determined as a
function of $x|_{S_{i}}$. This means that for every value of $x|_{S_{i}}$, the
only output bit that is not yet fixed is $f(x|_{S_{i}})$, which can be fixed
paying only _one bit of information_.

If we were to beat the hybrid argument, and construct a new black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proof that
works directly from worst-case hard functions, we would have to come close to
this behavior, and we hope that understanding this property may point us to
new constructions, potentially utilizing the ability to ask a small number of
queries (but more than just one query).

##### The Shaltiel-Umans PRG.

The Shaltiel-Umans PRG is a black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proof
$(\mathsf{Con}^{SU},\mathsf{Red}^{SU})$ with parameters $\ell,r,m,a,\rho=1$
and $\epsilon=\frac{1}{10}$, such that $\mathsf{Red}$ makes $q=m^{O(1)}$
queries.

Unlike the Nisan-Wigderson PRG, the Shaltiel-Umans PRG is stated for $\rho=1$
(starting from worst-case hard functions). Nevertheless, the Shaltiel-Umans
PRG builds on the hardness amplification techniques of Sudan, Trevisan and
Vadhan [STV01] and makes $q\geq m$ queries. Furthermore, it implies hardness
amplification to $\frac{1}{2}+\frac{1}{m}$. This means that it is not
applicable at the extreme high-end.

By Theorem 3.1, we have that:

$\operatorname{Fix}_{j}(\mathsf{Con}^{SU})\leq a+j\cdot(O(\log m)),$

for many values of $m$ and $j$.

Let us review how $\mathsf{Con}^{SU}$ achieves this. The construction
$\mathsf{Con}^{SU}_{f}$ relies on (a carefully chosen) black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{(\frac{1}{2}+\frac{1}{m})}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$
proof (which has additional structure). This hardness amplification
construction converts the worst-case hard function
$f:\\{0,1\\}^{\ell}\to\\{0,1\\}$ into an average case hard function
$f^{\prime}:\\{0,1\\}^{\ell^{\prime}}\to\\{0,1\\}$.

The PRG construction is then defined by setting $r=\ell^{\prime}$ and
defining:

$\mathsf{Con}^{SU}_{f}(x)=f^{\prime}(x),f^{\prime}(g(x)),f^{\prime}(g(g(x))),\ldots,f^{\prime}(g^{(m-1)}(x),$

where $g:\\{0,1\\}^{\ell^{\prime}}\to\\{0,1\\}^{\ell^{\prime}}$ is some
specific function. Another version that is often considered is a “seed
extending” version
$\overline{\mathsf{Con}}^{SU}_{f}(x)=x,\mathsf{Con}^{SU}_{f}(x)$ that outputs
$m+r$ bits.

This means that for every seed $x\in\\{0,1\\}^{\ell^{\prime}}$ if we consider
the $\ell$ “consecutive” seeds,

$g(x),g(g(x)),\ldots,g^{(m-1)}(x),$

all the outputs of $\mathsf{Con}^{SU}_{f}$ on these seeds, depend only on the
values of $f^{\prime}$ on $g(x),g(g(x)),\ldots,g^{(2m)}(x)$. This means that
$m$ outputs of $\mathsf{Con}^{SU}_{f}$ can be fixed at the cost of fixing $2m$
bits of $f^{\prime}$. In particular, for $j=a$ we get that $j=a$ outputs of
$\mathsf{Con}_{f}$ can be fixed at the total cost of $2a=a+j\cdot 1$ bits of
information about $f$. This means that after paying a fixed cost of $a$, $a$
outputs can be fixed at amortized cost of one bit of information per output.
This can be used to show that:

$\operatorname{Fix}_{a}(\overline{\mathsf{Con}}^{SU})\leq a+a\cdot 1.$

Again, if we were to beat the hybrid argument, and construct a new black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proof that
works directly from worst-case hard functions, we may hope to take this
understanding, hoping to somehow avoid paying the price of hardness
amplification to extremely hard on average functions.

###  3.2 Limitations on the “PEG + Extractor” approach of [DMOZ20]

In this section we restate Theorem 1.14 and discuss its consequences and
interpretation.

####  3.2.1 Limitation on black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PEG}$ constructions
with short seed

##### Review of the setup of Theorem 1.14.

Theorem 1.11 shows that for any black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PEG}$ proof
$(\mathsf{Con},\mathsf{Red})$, if $\mathsf{Red}$ is useful, and makes $q\leq
2^{\ell}$ queries, then $r\geq(1-o(1))\cdot\ell\geq(1-o(1))\cdot\log m$. As
explained in Section 1.3.2, this shows that the “PEG + extractor” approach of
[DMOZ20] cannot be used to obtain an extreme high-end PRG from the extreme
high-end hardness assumption if the PEG is constructed by a black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PEG}$ proof.

##### Formal definition of black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PEG}$ proofs.

In the introduction, we did not give a formal definition of black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PEG}$ proofs (and
only explained how these are defined in relation to black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PRG}$ proofs. We
therefore start with a formal definition.

######  Definition 3.7 (Black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow\mathsf{PEG}$ proof).

Given parameters $\ell,r,m,a,k,\epsilon,\rho$ a black-box
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow({k},{\epsilon})\mbox{-}\mathsf{PEG}$
proof is a pair $(\mathsf{Con},\mathsf{Red})$ of:

  * •

A construction map $\mathsf{Con}:\mathcal{F}_{\ell,1}\to\mathcal{F}_{r,m}$.

  * •

An oracle procedure $\mathsf{Red}^{(\cdot)}(x,\alpha)$ such that for every
$f\in\mathcal{F}_{\ell,1}$ and for every $D\in\mathcal{F}_{m,1}$ such that $D$
$(k,\epsilon)$-$\mathsf{PEG}\mbox{-}\mathsf{breaks}$ $\mathsf{Con}_{f}$, there
exists $\alpha\in\\{0,1\\}^{a}$ such that the function
$C\in\mathcal{F}_{\ell,1}$ defined by $C(x)=\mathsf{Red}^{D}(x,\alpha)$,
$\rho$-$\mathsf{hard}\mbox{-}\mathsf{function}\mbox{-}\mathsf{breaks}$ $f$.

If we omit $\rho$, we mean $\rho=1$. If we omit $\epsilon$, we mean
$\epsilon=1/10$. We say that $\mathsf{Red}$ makes $q$ queries, if for every
$D\in\mathcal{F}_{m,1}$, $\alpha\in\\{0,1\\}^{a}$, and $x\in\\{0,1\\}^{\ell}$,
$\mathsf{Red}^{D}(x,\alpha)$ makes at most $q$ oracle queries.

##### A more general statement.

The following Theorem is a generalized version of Theorem 1.14 which also
allows the parameter $\rho$ (measuring how hard on average is the function we
start from) to be very close to $\frac{1}{2}$.

######  Theorem 3.8.

There exists constants $\nu>0$ and $c>1$ such that for every black-box
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow({k},{\epsilon})\mbox{-}\mathsf{PEG}$
proof $(\mathsf{Con},\mathsf{Red})$ with parameters
$\ell,r,m,a,k,\epsilon,\rho$ such that

$r<\ell-\log\ell-2\cdot\log\frac{1}{\eta}-c.$

If $\rho=\frac{1}{2}+\eta$, $\eta\geq 2^{-\ell}$, $k>r$, $\epsilon\leq
1-2^{r-m}$, and $a\leq\nu\cdot\eta^{2}\cdot 2^{\ell}$, then $\mathsf{Red}$
must make at least $q>2^{\ell}$ queries.

##### A discussion of the parameters of Theorem 3.8.

The parameters in Theorems 1.14 and Theorem 3.8 are applicable even for very
large $a$, and therefore Theorem 3.1 applies in the extreme high-end (where
$a=2^{(1-o(1))\cdot\ell}$) as well as in less challenging ranges such as the
high-end (where $a=2^{\nu\cdot\ell}$ for a constant $\nu>0$) and the low-end
(where $a=\operatorname{poly}(\ell)$). We stress once again that to the best
of our knowledge, no known lower bound on the number of queries of a black-box
reduction (of any kind) applies in the extreme high-end. See Section 4 for a
discussion on past lower bounds on the number of queries by reductions for
black-box hardness amplification proofs.

We also note that the requirements on the parameters in Theorem 3.8 are quite
mild. We allow $\epsilon$ to approach one (rather than zero) and $k$ to
approach $r$ (rather than $m$). For $\rho=1$ (namely, starting from a worst-
case hard functions) we have that $\eta=\frac{1}{2}$ and the theorem works
even for $a=\Omega(2^{\ell})$.

###  3.3 Proofs of Theorem 3.1 and Theorem 3.8

In this section we prove Theorem 3.1 and Theorem 3.8 (which in turn imply
Theorem 1.11 and Theorem 1.14). Both Theorems will follow from the following
theorem (which can be seen as a version of Theorem 3.1 for PEGs).

######  Theorem 3.9.

There exists a constant $\nu>0$ such that for every black-box
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow({k},{\epsilon})\mbox{-}\mathsf{PEG}$
proof $(\mathsf{Con},\mathsf{Red})$ with parameters
$\ell,r,m,a,k,\epsilon,\rho$ such that $\mathsf{Red}$ makes at most $q\leq
2^{\ell}$ queries. If $\rho=\frac{1}{2}+\eta$, $\eta\geq 2^{-\ell}$, $k>r$,
$\epsilon\leq 1-2^{r-m}$, and $a\leq\nu\cdot\eta^{2}\cdot 2^{\ell}$, then for
$j_{\max}=\nu\cdot\frac{\eta^{2}\cdot 2^{\ell}}{\ell}$, and every $j\leq
j_{\max}$,

$\operatorname{Fix}_{j}(\mathsf{Con})\leq a+j\cdot(\log
q+\log\frac{4}{\eta}).$

The proof of Theorem 3.9 is given in Section 3.3.1.

##### Theorem 3.1 follows from Theorem 3.9.

Loosely speaking, this follows because any PRG is also a PEG, and therefore
limitations on PEGs also hold for PRGs. More formally, any black-box
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{\epsilon}\mbox{-}\mathsf{PRG}$
proof $(\mathsf{Con},\mathsf{Red})$ in which $\epsilon=1-2^{r-m}$ is also a
black-box
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow({k},{\epsilon})\mbox{-}\mathsf{PEG}$
proof for $k=r$. Theorem 3.9 applies for the latter, and therefore also
applies for the former, proving Theorem 3.1.

##### Theorem 3.8 follows from Theorem 3.9.

The conditions in Theorem 3.8 satisfy the conditions of Theorem 3.9 except for
the requirement made in Theorem 3.9 that $q\leq 2^{\ell}$. Therefore, under
the conditions of Theorem 3.9 we can apply Theorem 3.9 and conclude that
either $q>2^{\ell}$ or the conclusion of Theorem 3.9 holds and for
$j_{\max}=\nu\cdot\frac{\eta^{2}\cdot 2^{\ell}}{\ell}$, and every $j\leq
j_{\max}$, $\operatorname{Fix}_{j}(\mathsf{Con})\leq a+j\cdot(\log
q+\log\frac{4}{\eta})$. However, the latter option cannot happen. This is
because by the restriction on $r$, we get that $2^{r}<j_{\max}$. As the number
of outputs of $\mathsf{Con}_{f}$ is $2^{r}<j_{\max}$, it is impossible to fix
$j_{\max}$ distinct outputs, and so $\operatorname{Fix}_{j}(\mathsf{Con})$ is
undefined and can be viewed as infinity. Consequently, it can’t be the case
that $\operatorname{Fix}_{j}(\mathsf{Con})$ is smaller than some finite
quantity. We conclude that $q>2^{\ell}$.

####  3.3.1 Proof of Theorem 3.9

In this section we prove Theorem 3.9. We assume the assumption of Theorem 3.9,
namely that $(\mathsf{Con},\mathsf{Red})$ is a black-box
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow({k},{\epsilon})\mbox{-}\mathsf{PEG}$
proof that satisfies the conditions of Theorem 3.9. We first define a simple
distinguisher that answers one iff its input is a pseudorandom string.

######  Definition 3.10 (The simple distinguisher).

For every $f\in\mathcal{F}_{\ell,1}$ we define
$D_{f}:\\{0,1\\}^{m}\to\\{0,1\\}$ by:

$D_{f}(z)=\left\\{\begin{array}[]{ll}1,&\exists y\in\\{0,1\\}^{r}\mbox{ s.t.\
}\mathsf{Con}_{f}(y)=z\\\ 0,&\mbox{otherwise}\end{array}\right.$

######  Claim 3.11.

There exists $\alpha^{\prime}\in\\{0,1\\}^{a}$ and
$A_{0}\subseteq\mathcal{F}_{\ell,1}$ such that:

  1. 1.

$\Pr_{F\leftarrow\mathcal{F}_{\ell,1}}[F\in A_{0}]\geq 2^{-a}$.

  2. 2.

For every $f\in A_{0}$, the function $C_{f}:\\{0,1\\}^{\ell}\to\\{0,1\\}$
defined by $C_{f}(x)=\mathsf{Red}^{D_{f}}(x,\alpha^{\prime})$, satisfies that
$C_{f}$
$\rho\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\mbox{-}\mathsf{breaks}$
the function $f$.

###### Proof.

For every $f\in\mathcal{F}_{\ell,1}$,
$\Pr[D_{f}(\mathsf{Con}_{f}(U_{r}))=1]=1$, and $\Pr[D_{f}(U_{m})=1]\leq
2^{r-m}$. Therefore, $D_{f}$
$(k,\epsilon)-\mathsf{PEG}\mbox{-}\mathsf{breaks}$ $\mathsf{Con}_{f}$ if $k>r$
and $\epsilon\geq 1-2^{r-m}$, which is assumed in the statement of Theorem
3.9. By the definition of black-box
${\rho}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow({k},{\epsilon})\mbox{-}\mathsf{PEG}$
proof, we have that for every $f\in\mathcal{F}_{\ell,1}$, as $D_{f}$
$(k,\epsilon)$-$\mathsf{PEG}\mbox{-}\mathsf{breaks}$ $\mathsf{Con}_{f}$, there
exists $\alpha\in\\{0,1\\}^{a}$ such that the function
$C\in\mathcal{F}_{\ell,1}$ defined by $C(x)=\mathsf{Red}^{D}(x,\alpha)$,
$\rho$-$\mathsf{hard}\mbox{-}\mathsf{function}\mbox{-}\mathsf{breaks}$ $f$.
Therefore, by averaging, there exists $\alpha^{\prime}\in\\{0,1\\}^{a}$ that
works for a $2^{-a}$ fraction of the functions $f\in\mathcal{F}_{\ell,1}$, and
let $A_{0}$ denote the subset of all functions $f\in\mathcal{F}_{\ell,1}$ for
which $\alpha^{\prime}$ works. ∎

We will now define a function $C:\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}$ (that
does not depend on $f$) with the hope of showing that if the conclusion of
Theorem 3.9 does not hold, then $C(x)$ simulates
$\mathsf{Red}^{D_{f}}(x,\alpha^{\prime})$ quite well for “some” choices of
$f\in\mathcal{F}_{\ell,1}$ and $x\in\\{0,1\\}^{\ell}$.

######  Definition 3.12.

For every $x\in\\{0,1\\}^{\ell}$, we define
$z^{x}_{1},\ldots,z^{x}_{q}\in\\{0,1\\}^{m}$ as follows: We consider an
invocation of $\mathsf{Red}^{(\cdot)}(x,\alpha^{\prime})$ in which all queries
are answered by zero, and for $1\leq i\leq q$, let $z^{x}_{i}$ denote the
$j$’th query made by $\mathsf{Red}(x,\alpha^{\prime})$ in this invocation. Let
$C(x)$ denote the output of $\mathsf{Red}(x,\alpha^{\prime})$ in this
invocation.

Note that $z^{x}_{1},\ldots,z^{x}_{q}\in\\{0,1\\}^{m}$ do not depend on the
choice of the function $D$ given to $\mathsf{Red}$ as oracle. We will be
interested in the case that $\mathsf{Red}$ gets oracle access to the function
$D_{f}$, for some $f\in\mathcal{F}_{\ell,1}$. Note that for every
$f\in\mathcal{F}_{\ell,1}$, $z^{x}_{1}$ is the first query made by
$\mathsf{Red}^{D_{f}}(x,\alpha^{\prime})$, and for $i>1$, $z^{x}_{i}$ may be
different than the $i$’th query made by
$\mathsf{Red}^{D_{f}}(x,\alpha^{\prime})$), as the reduction is allowed to
make adaptive queries. Nevertheless, the following obviously holds:

######  Claim 3.13.

For every $f\in\mathcal{F}_{\ell,1}$ and every $x\in\\{0,1\\}^{\ell}$, if
$D_{f}(z^{x}_{1})=\ldots=D_{f}(z^{x}_{q})=0$ then
$C(x)=\mathsf{Red}^{D_{f}}(x,\alpha^{\prime})$.

By definition, for every $f\in\mathcal{F}_{\ell,1}$, we have that the number
of $z\in\\{0,1\\}^{m}$ on which $D_{f}$ answers one is small (at most
$2^{r}$). We will say that a $z\in\\{0,1\\}^{m}$ is _weak_ with respect to
some $A\subseteq\mathcal{F}_{\ell,1}$, if it is likely that $D_{f}(z)=1$ when
$f$ is chosen uniformly in $A$.

######  Definition 3.14.

We say that $z\in\\{0,1\\}^{m}$ is $t$-weak with respect to a set
$A\subseteq\mathcal{F}_{\ell,1}$ if

$\Pr_{F\leftarrow A}[D_{F}(z)=1]\geq 2^{-t}.$

We will now consider an iterative process in which we will iteratively fix
outputs $z$ of $\mathsf{Con}$ that are weak.

More precisely, we set $t=\log\frac{4\cdot q}{\eta}$ and consider the
following iterative process. We start with the set $A_{0}$ that we already
obtained, and $W_{0}=\emptyset$. We will maintain the following invariant:

Invariant:

At step $j$ we maintain that:

  1. 1.

$\Pr_{F\leftarrow\mathcal{F}_{\ell,1}}[F\in A_{j}]\geq 2^{-(a+jt)}$.

  2. 2.

$A_{j}\subseteq A_{0}$.

  3. 3.

$|W_{j}|=j$.

  4. 4.

For every $z\in W_{j}$ and every $f\in A_{j}$, $D_{f}(z)=1$.

Note that this invariant indeed holds for $j=0$. At step $0<j<j_{\max}$ we do
the following: If there does not exist a $z\not\in W_{j-1}$ that is $t$-weak
with respect to $A_{j-1}$ then the process stops. Otherwise, if there exists
$z\not\in W_{j-1}$ that is $t$-weak with respect to $A_{j-1}$, we define:

  * •

$W_{j}=W_{j-1}\cup\left\\{{z}\right\\}$.

  * •

$A_{j}=\left\\{{f\in A_{j-1}:D_{f}(z)=1}\right\\}$.

We observe that the invariant is indeed kept throughout this process.

######  Claim 3.15.

For every $j\leq j_{max}$ for which the process has not yet stopped, the
invariant above holds.

###### Proof.

This is obvious for the second, third and fourth items. The first item follows
because for every $j$ if the process did not stop before step $j$, then
$A_{j}$ exists, and we have that:

$\displaystyle\Pr_{F\leftarrow\mathcal{F}_{\ell,1}}[F\in A_{j}]$
$\displaystyle=\Pr_{F\leftarrow\mathcal{F}_{\ell,1}}[F\in A_{j}|F\in
A_{j-1}]\cdot\Pr_{F\leftarrow\mathcal{F}_{\ell,1}}[F\in A_{j-1}]$
$\displaystyle\geq\Pr_{F\leftarrow A_{j-1}}[F\in A_{j}]\cdot 2^{-(a+(j-1)\cdot
t)}$ $\displaystyle\geq 2^{-t}\cdot 2^{-(a+(j-1)\cdot t)}$ $\displaystyle\geq
2^{-(a+j\cdot t)},$

where the third line is using $t$-weakness. ∎

######  Claim 3.16.

If the process stops at some $j^{*}<j_{max}$, then there exists $A\subseteq
A_{0}$ such that:

  1. 1.

$\Pr_{F\leftarrow\mathcal{F}_{\ell,1}}[F\in A]\geq 2^{-(a+j^{*}\cdot t)+1}$.

  2. 2.

$\Pr_{F\leftarrow
A,X\in\\{0,1\\}^{\ell}}[C(X)=F(X)]\geq\frac{1}{2}+\frac{\eta}{2}$.

###### Proof.

If the process stopped at some $j^{*}<j_{max}$, then there does not exist a
$z\not\in W_{j^{*}}$ that is $t$-weak with respect to $A_{j^{*}}$. This in
particular means that for every $x\in\\{0,1\\}^{\ell}$,
$z^{x}_{1},\ldots,z^{x}_{q}$ are not $t$-weak with respect to $A_{j^{*}}$ and
therefore, by a union bound:

$\Pr_{F\leftarrow A_{j^{*}}}[\exists i\in[q]:D_{F}(z^{x}_{i})=1]\leq q\cdot
2^{-t}\leq\frac{\eta}{4},$

which means that:

$\Pr_{F\leftarrow A_{j^{*}}}[\forall i\in[q]:D_{F}(z^{x}_{i})=0]\geq
1-\frac{\eta}{4},$

by Claim 3.13 we conclude that for every $x\in\\{0,1\\}^{\ell}$,

$\Pr_{F\leftarrow A_{j^{*}}}[C(x)=\mathsf{Red}^{D_{F}}(x,\alpha^{\prime})]\geq
1-\frac{\eta}{4}.$

For every $x\in\\{0,1\\}^{\ell}$, let $V_{x}$ denote the random variable (over
the probability space of $F\leftarrow A_{j^{*}}$) defined by:

$V_{x}=\left\\{\begin{array}[]{ll}1,&C(x)\neq\mathsf{Red}^{D_{F}}(x,\alpha^{\prime})\\\
0,&\mbox{otherwise}\end{array}\right.$

Let $V=\sum_{x\in\\{0,1\\}^{\ell}}V_{x}$. It follows that
$\operatorname*{\mathbb{E}}_{F\leftarrow A_{j^{*}}}[V]\leq
2^{\ell}\cdot\frac{\eta}{4}$. By Markov’s inequality we have that:

$\Pr_{F\leftarrow A_{j^{*}}}[V>2^{\ell}\cdot\frac{\eta}{2}]<\frac{1}{2}.$

Let $A=\left\\{{f\in A_{j^{*}}:V\leq 2^{\ell}\cdot\frac{\eta}{2}}\right\\}$.
It follows that:

$\Pr_{F\leftarrow\mathcal{F}_{\ell,1}}[F\in
A]\geq\frac{1}{2}\cdot\Pr_{F\leftarrow\mathcal{F}_{\ell,1}}[F\in
A_{j^{*}}]\geq 2^{-(a+j^{*}\cdot t)+1}.$

For every $f\in A$, we have that the fraction of inputs $x\in\\{0,1\\}^{\ell}$
on which $V_{x}(f)=1$ (meaning that
$C(x)\neq\mathsf{Red}^{D_{f}}(x,\alpha^{\prime})$) is
$\frac{V(f)}{2^{\ell}}\leq\frac{\eta}{2}$. This means that when we choose both
$F\leftarrow A$ and $X\leftarrow\\{0,1\\}^{\ell}$ independently, we have that:

$\Pr_{F\leftarrow
A,X\leftarrow\\{0,1\\}^{\ell}}[C(X)\neq\mathsf{Red}^{D_{F}}(X,\alpha^{\prime})]\leq\frac{\eta}{2}.$

On the other hand, as $A\subseteq A_{j^{*}}\subseteq A_{0}$, by Claim 3.11 we
have that for every $f\in A$, the function
$C_{f}:\\{0,1\\}^{\ell}\to\\{0,1\\}$ defined by
$C_{f}(x)=\mathsf{Red}^{D_{f}}(x,\alpha^{\prime})$, satisfies that $C_{f}$
$\rho$-$\mathsf{hard}\mbox{-}\mathsf{function}\mbox{-}\mathsf{breaks}$ the
function $f$. This means that for every $f\in A$,

$\Pr_{X\leftarrow\\{0,1\\}^{\ell}}[\mathsf{Red}^{D_{f}}(X,\alpha^{\prime})=f(X)]\geq\rho.$

This means that when we choose both $F\leftarrow A$ and
$X\leftarrow\\{0,1\\}^{\ell}$ independently, we have that:

$\Pr_{F\leftarrow
A,X\leftarrow\\{0,1\\}^{\ell}}[\mathsf{Red}^{D_{F}}(X,\alpha^{\prime})=F(X)]\geq\rho.$

Putting things together, we have that:

$\Pr_{F\leftarrow
A,X\leftarrow\\{0,1\\}^{\ell}}[C(X)=F(X)]\geq\rho-\frac{\eta}{2}=\frac{1}{2}+\frac{\eta}{2}.$

∎

However, the next claim shows that if $A$ is a large set, it is unlikely that
a single function $C$ is a good approximation to $F\leftarrow A$.

######  Claim 3.17.

For every $A\subseteq\mathcal{F}_{\ell,1}$, and every function
$C:\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}$, if
$\Pr_{F\leftarrow\mathcal{F}_{\ell,1}}[F\in A]\geq 2^{-\Delta}$ then

$\Pr_{F\leftarrow
A,X\leftarrow\\{0,1\\}^{\ell}}[C(X)=F(X)]=\frac{1}{2}+O\left(\sqrt{\frac{\Delta+\ell}{2^{\ell}}}\right).$

###### Proof.

For the purpose of contradiction we will set
$\lambda=\Omega\left(\sqrt{\frac{\Delta+\ell}{2^{\ell}}}\right)$, and assume
that

$\Pr_{F\leftarrow
A,X\leftarrow\\{0,1\\}^{\ell}}[C(X)=F(X)]\geq\frac{1}{2}+\lambda.$

By an averaging argument, it follows that:

$\Pr_{F\leftarrow
A}\left[\Pr_{X\leftarrow\\{0,1\\}^{\ell}}[C(X)=F(X)]\geq\frac{1}{2}+\frac{\lambda}{2}\right]\geq\frac{\lambda}{2}.$

Let $A^{\prime}\subseteq A$ be the subset defined as follows:

$A^{\prime}=\left\\{{f\in
A:\Pr_{X\leftarrow\\{0,1\\}^{\ell}}[C(X)=f(X)]\geq\frac{1}{2}+\frac{\lambda}{2}}\right\\}.$

It follows that $|A^{\prime}|\geq\frac{\lambda}{2}\cdot|A|$. For every
function $C\in\mathcal{F}_{\ell,1}$, the number of $f\in\mathcal{F}_{\ell,1}$
such that
$\Pr_{X\leftarrow\\{0,1\\}^{\ell}}[C(X)=f(X)]\geq\frac{1}{2}+\frac{\lambda}{2}$
is bounded by the size of a Hamming ball in $\\{0,1\\}^{2^{\ell}}$ that is of
radius $(\frac{1}{2}-\frac{\lambda}{2})\cdot 2^{\ell}$. The latter quantity is
bounded by $2^{H(\frac{1}{2}-\lambda/2)\cdot 2^{\ell}}\leq
2^{(1-O(\lambda^{2}))\cdot 2^{\ell}}$ where $H(\cdot)$ is Shannon’s binary
entropy function, and using the fact that
$H(\frac{1}{2}-\lambda)=1-O(\lambda^{2})$. We conclude that there exists a
constant $c>1$ such that:

$|A|\leq\frac{2}{\lambda}\cdot|A^{\prime}|\leq\frac{2}{\lambda}\cdot
2^{(1-c\cdot\lambda^{2})\cdot
2^{\ell}}=2^{\log(\frac{1}{\lambda})+1+(1-c\cdot\lambda^{2})\cdot
2^{\ell}}=2^{2^{\ell}-(c\cdot\lambda^{2}\cdot 2^{\ell}-\log(1/\lambda)-1)}.$

We also have that $|A|\geq 2^{2^{\ell}-\Delta}$, and so we conclude that
$\Delta>c\cdot\lambda^{2}\cdot 2^{\ell}-\log(1/\lambda)-1$. This gives a
contradiction if
$\lambda=\Omega\left(\sqrt{\frac{\Delta+\ell}{2^{\ell}}}\right)$. ∎

Putting Claim 3.16 and Claim 3.17 together, we get that:

######  Claim 3.18.

The iterative process does not stop until $j=j_{\max}$.

###### Proof.

By Claim 3.16 and Claim 3.17, we conclude that if the process stops at some
$j^{*}<j_{max}$ then there exists a constant $c>1$ such that:

$\frac{1}{2}+c\cdot\sqrt{\frac{a+j^{*}\cdot
t+\ell}{2^{\ell}}}\geq\frac{1}{2}+\frac{\eta}{2},$

Recalling that $t=\log\frac{4q}{\eta}$ this gives that:

$\displaystyle q$ $\displaystyle\geq\frac{\eta}{4}\cdot
2^{\frac{\frac{2^{\ell}\cdot\eta^{2}}{4c}-a-\ell}{j^{*}}}$
$\displaystyle\geq\frac{\eta}{4}\cdot
2^{\frac{\frac{2^{\ell}\cdot\eta^{2}}{5c}}{j^{*}}}$ $\displaystyle>2^{\ell},$

where the first inequality follows because we have that
$a\leq\nu\cdot\eta^{2}\cdot 2^{\ell}$, and we can choose the constant $\nu>0$
to be sufficiently small. The second inequality follows because $\eta\geq
2^{-\ell}$, and $j^{*}\leq j_{\max}\leq\nu\cdot\frac{\eta^{2}\cdot
2^{\ell}}{\ell}$, and we can choose $\nu>0$ to be sufficiently small.

Therefore, as we are assuming that $q\leq 2^{\ell}$, it is a contradiction if
the process stops at some $j^{*}<j_{\max}$. ∎

As the process did not stop at any $j<j_{\max}$, then for every $j\leq
j_{\max}$, the sets $A_{j},W_{j}$ are defined, and by Claim 3.15 they maintain
the invariant.

By the invariant, for every $j\leq j_{\max}$ we conclude that for every $z\in
W_{j}$ and every $f\in A_{j}$, $D_{f}(z)=1$ (meaning that there exists
$y\in\\{0,1\\}^{r}$ such that $z$ is an output of $\mathsf{Con}_{f})$. By the
invariant, we know that $|W_{j}|=j$ therefore, if we denote the elements of
$W_{j}$ by $z_{1},\ldots,z_{j}\in\\{0,1\\}^{m}$ we conclude that for every
$f\in A_{j}$, and every $i\in[j]$ there exists $y_{i}\in\\{0,1\\}^{r}$ (that
may depend on $f$) such that $\mathsf{Con}_{f}(y_{i})=z_{i}$. From the
invariant, we also have that:

$\Pr_{F\leftarrow\mathcal{F}_{\ell,1}}[F\in A_{j}]\geq 2^{-(a+j\cdot
t)}=2^{-(a+j\cdot(\log q+\log\frac{4}{\eta}))}.$

Putting everything together we get that:

$\Pr_{F\leftarrow\mathcal{F}_{\ell,1}}[\forall i\in[j]:\exists
y_{i}\in\\{0,1\\}^{r}\mbox{ s.t. }\mathsf{Con}_{F}(y_{i})=z_{i}]\geq
2^{-(a+j\cdot(\log q+\log\frac{4}{\eta}))},$

which gives that for every $j\leq j_{\max}$,
$\operatorname{Fix}_{j}(\mathsf{Con})\leq a+j\cdot(\log
q+\log\frac{4}{\eta})$. This proves Theorem 3.9.

##  4 Limitations on black-box hardness amplification at the extreme high-end

In this section we prove Theorem 1.15 showing that reductions for black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{(\frac{1}{2}+\epsilon)}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$
proofs must make many queries, even at the extreme high-end. Theorem 1.15 is a
combination of two lower bounds, stated next:

######  Theorem 4.1 (Lower bound in terms of $\epsilon$).

If $(\mathsf{Con},\mathsf{Red})$ is a
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{(\frac{1}{2}+\epsilon)}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$
proof with parameters
$\ell,\ell^{\prime},a,\rho=1,\rho^{\prime}=\frac{1}{2}+\epsilon$, satisfying
$a\leq\frac{2^{\ell}}{10}$ and
$\ell^{\prime}\geq\log\frac{1}{\epsilon^{2}}+\Omega(1)$ then $\mathsf{Red}$
must make at least $q=\Omega(\frac{1}{\epsilon})$ queries.

######  Theorem 4.2 (Lower bound in terms of $\ell$).

If $(\mathsf{Con},\mathsf{Red})$ is a
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{(\frac{1}{2}+\epsilon)}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$
proof with parameters
$\ell,\ell^{\prime},a,\rho=1,\rho^{\prime}=\frac{1}{2}+\epsilon$, satisfying
$\epsilon\leq\frac{1}{10}$, and
$\ell^{\prime}\geq\log\frac{1}{\epsilon^{2}}+\Omega(1)$ then $\mathsf{Red}$
must make at least $q\geq\frac{\ell-\log(2a)}{3}$ queries

A quantitatively better lower bound of $q=\Omega(\frac{\ell}{\epsilon^{2}})$
was proven by Grinberg, Shaltiel and Viola [GSV18] for the case that $a\leq
2^{\nu\cdot\ell}$ for some constant $\nu>0$. Theorems 4.1 and Theorem 4.2
achieve a smaller bound on $q$, but apply in the extreme high-end (where
$a=2^{(1-o(1))\cdot\ell}$) all the way up to $a=\frac{2^{\ell}}{10}$. This is
especially significant in the case of Theorem 4.1 which (as we explained in
detail in Section 1.3.4) can be used to show limitations on the PRG
composition of Chen and Tell [CT21b].

##### Roadmap for this section.

Both Theorem 4.1 and Theorem 4.2 will be proven by first connecting a black-
box reduction to a depth 3 circuit for a version of the “coin problem”. This
connection is stated and proven in Section 4.1. The proofs of Theorem 4.1 and
Theorem 4.2 show that such a depth 3 circuit must have large $q$. These proofs
are given in Section 4.2 and Section 4.3.

###  4.1 Reductions as depth 3 circuits

The proof of Theorem 4.1 and Theorem 4.2 rely on the following lemma, which is
inspired by an argument of Applebaum et al. [AASY16] (see also [RSV21]) and
relates black-box reductions to constant depth circuits.

######  Lemma 4.3 (Reduction to circuit).

Let $(\mathsf{Con},\mathsf{Red})$ be a black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{(\frac{1}{2}+\epsilon)}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$
proof with parameters
$\ell,\ell^{\prime},a,\rho=1,\rho^{\prime}=\frac{1}{2}+\epsilon$, such that
$\mathsf{Red}$ makes $q$ queries. For every $\alpha\in\\{0,1\\}^{a}$, there
exists a $q$-CNF $C^{\alpha}$ with $2^{q+\ell}$ clauses, over
$n=2^{\ell^{\prime}}$ variables, such that for
$C=\bigvee_{\alpha\in\\{0,1\\}^{a}}C^{\alpha}$, we have that:

  * •

$\Pr[C(U_{n})]\leq 2^{-(2^{\ell}-a)}$.

  * •

For every $x\in\\{0,1\\}^{n}$ such that
$\operatorname{weight}(x)\leq(\frac{1}{2}-\epsilon)\cdot n$, $C(x)=1$.

###### Proof.

We will view a string $z$ of length $n=2^{\ell^{\prime}}$, as a function
$z\in\mathcal{F}_{\ell^{\prime},1}$ and vice-versa, by $z(y)=z_{y}$. The proof
of [AASY16] (and the proof presented here) makes use of an idea originating in
[Vio06, SV10] (and credited to Madhu Sudan) that the reduction must succeed if
given oracle access to $\mathsf{Con}_{f}\oplus z$ for a string $z$ with
$\operatorname{weight}(z)\leq n\cdot(\frac{1}{2}-\epsilon)$ (as such an oracle
$(\frac{1}{2}+\epsilon)$-$\mathsf{hard}\mbox{-}\mathsf{function}\mbox{-}\mathsf{breaks}$
$\mathsf{Con}_{f}$), but cannot succeed when given oracle access to
$\mathsf{Con}_{f}\oplus z$ for $z\leftarrow U_{n}$ (as $z$ “wipes out” the
information in $\mathsf{Con}_{f}$). This will translate into the two
conditions in the lemma. Details follow:

For every $f\in\mathcal{F}_{\ell,1}$, $\alpha\in\\{0,1\\}^{a}$ and
$x\in\\{0,1\\}^{\ell}$, we define $C_{f,\alpha,x}:\\{0,1\\}^{n}\to\\{0,1\\}$
as follows:

$C_{f,\alpha,x}(z)=1\mbox{ iff $\mathsf{Red}^{\mathsf{Con}_{f}\oplus
z}(x,\alpha)=f(x)$.}$

We have that $\mathsf{Red}$ makes at most $q$ queries, and this implies that
for every $f$ and $\alpha$, the function $C_{f,\alpha}$ can be computed by a
decision tree with height $q$. Therefore, it can be computed by a $q$-CNF with
$2^{q}$ clauses. For every $f\in\mathcal{F}_{\ell,1}$, and
$\alpha\in\\{0,1\\}^{a}$ we define $C_{f,\alpha}:\\{0,1\\}^{n}\to\\{0,1\\}$ as
follows:

$C_{f,\alpha}(z)=1\mbox{ iff $\forall x\in\\{0,1\\}^{\ell}$,
$\mathsf{Red}^{\mathsf{Con}_{f}\oplus z}(x,\alpha)=f(x)$.}$

By definition for every $f$ and $\alpha$,
$C_{f,\alpha}(x)=\bigwedge_{x\in\\{0,1\\}^{\ell}}C_{f,\alpha,x}$. This means
that $C_{f,\alpha}$ is an AND of $2^{\ell}$ $q$-CNFs with $2^{q}$ clauses, and
overall, it can be computed by a $q$-CNF with $2^{q+\ell}$ clauses. For every
$f\in\mathcal{F}_{\ell,1}$, we define $C_{f}:\\{0,1\\}^{n}\to\\{0,1\\}$ as
follows:

$C_{f,\alpha}(z)=1\mbox{ iff $\exists\alpha\in\\{0,1\\}^{a}$, s.t. $\forall
x\in\\{0,1\\}^{\ell}$, $\mathsf{Red}^{\mathsf{Con}_{f}\oplus
z}(x,\alpha)=f(x)$.}$

This gives that for every $f\in\mathcal{F}_{\ell,1}$, $C_{f}$ is an OR of
$2^{a}$ $q$-CNFs with $2^{q+\ell}$ clauses.

Furthermore, by the definition of black-box
$\mathsf{hard}\mbox{-}\mathsf{function}\Rightarrow{(\frac{1}{2}+\epsilon)}\mbox{-}\mathsf{hard}\mbox{-}\mathsf{function}$
proof, for every $f\in\mathcal{F}_{\ell,1}$, if
$\operatorname{weight}(z)\leq(\frac{1}{2}-\epsilon)\cdot n$, then the function
$\mathsf{Con}_{f}\oplus z$,
$\frac{1}{2}+\epsilon$-$\mathsf{hard}\mbox{-}\mathsf{function}\mbox{-}\mathsf{breaks}$
breaks $\mathsf{Con}_{f}$. This in turn implies (by Definition 1.7) that there
exists $\alpha\in\\{0,1\\}^{a}$ such that for every $x\in\\{0,1\\}^{\ell}$,
$\mathsf{Red}^{\mathsf{Con}_{f}\oplus z}(x)=f(x)$, meaning that $C_{f}(z)=1$.
This means that for every choice of $f\in\mathcal{F}_{\ell,1}$, $C_{f}$
satisfies the second item.

We will now show that there exists an $f\in\mathcal{F}_{\ell,1}$ such that
$C_{f}$ satisfies the first item. For a uniformly chosen $z\leftarrow U_{n}$,
we have that for every $f\in\mathcal{F}_{\ell,1}$, $\mathsf{Con}_{f}\oplus z$
is distributed uniformly over $\\{0,1\\}^{n}$, and contains no information
about $f$. It follows that:

$\displaystyle\Pr_{f\leftarrow\mathcal{F}_{\ell,1},z\leftarrow
U_{n}}[C_{f}(z)=1]$
$\displaystyle=\Pr_{F\leftarrow\mathcal{F}_{\ell,1},z\leftarrow
U_{n}}[\mbox{$\exists\alpha\in\\{0,1\\}^{a}$, s.t. $\forall
x\in\\{0,1\\}^{\ell}$, $\mathsf{Red}^{\mathsf{Con}_{f}\oplus
z}(x,\alpha)=f(x)$}]$
$\displaystyle=\Pr_{f\leftarrow\mathcal{F}_{\ell,1},z\leftarrow
U_{n}}[\mbox{$\exists\alpha\in\\{0,1\\}^{a}$, s.t. $\forall
x\in\\{0,1\\}^{\ell}$, $\mathsf{Red}^{z}(x,\alpha)=f(x)$}]$ $\displaystyle\leq
Pr_{f\leftarrow\mathcal{F}_{\ell,1}}[\mbox{$\exists\alpha\in\\{0,1\\}^{a}$,
s.t. $\forall x\in\\{0,1\\}^{\ell}$, $\mathsf{Red}^{z^{*}}(x,\alpha)=f(x)$}],$

for some $z^{*}\in\\{0,1\\}^{n}$ which maximizes the success probability. We
can therefore continue and obtain that:

$\displaystyle\Pr_{f\leftarrow\mathcal{F}_{\ell,1},z\leftarrow
U_{n}}[C_{f}(z)=1]$
$\displaystyle\leq\Pr_{F\leftarrow\mathcal{F}_{\ell,1}}[\mbox{$\exists\alpha\in\\{0,1\\}^{a}$,
s.t. $\forall x\in\\{0,1\\}^{\ell}$, $\mathsf{Red}^{z^{*}}(x,\alpha)=f(x)$},]$
$\displaystyle\leq\sum_{\alpha\in\\{0,1\\}^{a}}\Pr_{f\leftarrow\mathcal{F}_{\ell,1}}[\mbox{$\forall
x\in\\{0,1\\}^{\ell}$, $\mathsf{Red}^{z^{*}}(x,\alpha)=f(x)$}]$
$\displaystyle\leq 2^{a}\cdot\frac{1}{2^{2^{\ell}}},$

where the penultimate inequality follows by a union bound, and the last
inequality follows because for every $x\in\\{0,1\\}^{\ell}$,

$\Pr_{f\leftarrow\mathcal{F}_{\ell,1}}[\mathsf{Red}^{z^{*}}(x,\alpha)=f(x)]=\frac{1}{2},$

and these events are independent for the $2^{\ell}$ choices of
$x\in\\{0,1\\}^{\ell}$. Finally, by averaging, we conclude that there exists
$f\in\mathcal{F}_{\ell,1}$ such that:

$\Pr_{z\leftarrow U_{n}}[C_{f}(z)=1]\leq 2^{-(2^{\ell}-a)}.$

The final function $C$ will be this function $C_{f}$ which indeed satisfies
the properties in the conclusion of the lemma. ∎

###  4.2 Proof of Theorem 4.1

In this section we prove Theorem 4.1. We split the proof into two parts,
specified in Lemma 4.4 and Lemma 4.5 below. This splitting will allow us to
use Lemma 4.5 in the application to lower bounds on local list-decoding in
Section 5.

######  Lemma 4.4.

Assume the conditions of Theorem 4.1. For every $\alpha\in\\{0,1\\}^{a}$,
there exists a $q$-CNF $C^{\alpha}$ over $n=2^{\ell^{\prime}}$ variables, such
that for $C=\bigvee_{\alpha\in\\{0,1\\}^{a}}C^{\alpha}$, and
$p=\frac{\epsilon}{10}$:

  * •

$\Pr[C(U_{n})=1]\leq 2^{-(2^{\ell}-a)}$.

  * •

$\Pr_{\rho\leftarrow\mathsf{R}^{n}_{p}}[\Pr_{x\leftarrow U^{1/3}_{n\cdot
p}}[C(\operatorname{Fill}_{\rho}(x))=1]\geq 0.99]\geq 0.99$.

The next lemma shows that under (a weak form) of the conclusion of Lemma 4.4,
if $a$ is slightly smaller than $2^{\ell}$ then
$q=\Omega(\frac{1}{\epsilon})$.

######  Lemma 4.5.

Let $C$ be a circuit such that $C=\bigvee_{\alpha\in\\{0,1\\}^{a}}C^{\alpha}$,
where for each $\alpha\in\\{0,1\\}^{a}$, $C^{\alpha}$ is a $q$-CNF over $n$
variables. Let $p=\frac{\epsilon}{10}$ and assume that:

  * •

$\Pr[C(U_{n})=1]\leq 2^{-(2^{\ell}-a)}$.

  * •

$\Pr_{\rho\leftarrow\mathsf{R}^{n}_{p}}\left[\Pr_{x\leftarrow U^{1/3}_{n\cdot
p}}[C(\operatorname{Fill}_{\rho}(x))=1]\geq 0.01\right]\geq 0.01$.

  * •

$a\leq\frac{2^{\ell}}{10}$.

Then $q\geq\frac{1000}{\epsilon}$.

Together, Lemma 4.4 and Lemma 4.5 imply Theorem 4.1. The proofs of Lemma 4.4
and Lemma 4.5 are given in Sections 4.2.1 and 4.2.2.

####  4.2.1 Proof of Lemma 4.4

We first apply Lemma 4.3 and obtain that for every $\alpha\in\\{0,1\\}^{a}$,
there exists a $q$-CNF $C^{\alpha}$ over $n=2^{\ell^{\prime}}$ variables, such
that:

  * •

$\Pr[C^{\alpha}(U_{n})=1]\leq 2^{-(2^{\ell}-a)}$.

  * •

For every $x\in\\{0,1\\}^{n}$ such that
$\operatorname{weight}(x)\leq(\frac{1}{2}-\epsilon)\cdot n$, there exists
$\alpha\in\\{0,1\\}^{a}$ such that $C^{\alpha}(x)=1$.

When choosing $\rho\leftarrow\mathsf{R}^{n}_{p}$ we expect that
$\frac{1}{n}\cdot|\left\\{{i:\rho(i)=1}\right\\}|=\frac{1}{2}-\frac{p}{2}$.
Therefore, by a Chernoff bound:

$\Pr_{\rho\leftarrow\mathsf{R}^{n}_{p}}[\frac{1}{n}\cdot|\left\\{{i:\rho(i)=1}\right\\}|\geq\frac{1}{2}-0.49\cdot
p]\cdot\leq 2^{-\Omega(p^{2}\cdot n)},$

which is smaller than $0.01$, by the assumption that
$\ell^{\prime}\geq\log\frac{1}{\epsilon^{2}}+\Omega(1)$, and
$n=2^{\ell^{\prime}}$. If this event occurs, then for every
$x\in\\{0,1\\}^{n\cdot p}$,

$\operatorname{weight}(\operatorname{Fill}_{\rho}(x))\leq(\frac{1}{2}-0.49\cdot
p)\cdot n+\operatorname{weight}(x).$

This means that if $\operatorname{weight}(x)\leq 0.34\cdot p\cdot n$, then

$\operatorname{weight}(\operatorname{Fill}_{\rho}(x))\leq
n\cdot(\frac{1}{2}-(0.49-0.34)\cdot p)\leq n\cdot(\frac{1}{2}-\epsilon),$

By our assumption that $p\leq\frac{\epsilon}{10}$. Applying a Chernoff bound,
we conclude that:

$\Pr_{x\leftarrow U^{1/3}_{n\cdot p}}[\operatorname{weight}(x)\geq 0.34\cdot
p\cdot n]\leq 2^{-\Omega(pn)},$

which is smaller than $0.01$ by the assumption that
$\ell^{\prime}\geq\log\frac{1}{\epsilon^{2}}+\Omega(1)$, and
$n=2^{\ell^{\prime}}$.

####  4.2.2 Proof of Lemma 4.5

We want to show that following a random restriction, each $C^{\alpha}$ is a
low height decision tree.

######  Claim 4.6.

If $q<\frac{1000}{\epsilon}$ then there exists a restriction
$\rho:[n]\to\left\\{{0,1,*}\right\\}$ with $\operatorname{Free}(\rho)=n\cdot
p$ such that:

  * •

For every $\alpha\in\\{0,1\\}^{a}$, $C^{\alpha}_{\rho}$ is a decision tree of
height $a$.

  * •

$\Pr[C_{\rho}(U_{n})=1]\leq 2^{-(2^{\ell}-a-10)}$.

  * •

$\Pr[C_{\rho}(U^{1/3}_{n})=1]\geq 0.01$.

###### Proof.

We will show that when choosing $\rho\leftarrow\mathsf{R}^{n}_{p}$ there is a
positive probability to obtain a $\rho$ that satisfies all three items. This
will follow by a union bound in which we show that the probability that each
of the items does not hold is small.

For the first item, we note that by Theorem 2.3 for every
$\alpha\in\\{0,1\\}^{a}$, the probability over
$\rho\leftarrow\mathsf{R}^{n}_{p}$ that $C^{\alpha}_{\rho}$ does not have a
decision tree of height $a$, is at most $(7\cdot p\cdot
q)^{a}\leq(7/100)^{a}$. By a union bound over the $2^{a}$ choices of
$\alpha\in\\{0,1\\}^{a}$, the probability over
$\rho\leftarrow\mathsf{R}^{n}_{p}$ that there exists $\alpha\in\\{0,1\\}^{a}$
such that $C^{\alpha}_{\rho}$ does not have a decision tree of height $a$, is
at most $0.001$.

For the second item, we recall that by Lemma 4.4 we have that:
$\Pr[C(U_{n})=1]\leq 2^{-(2^{\ell}-a)}$. Therefore, by Markov’s in equality we
conclude that with probability at least $0.999$ over
$\rho\leftarrow\mathsf{R}^{n}_{p}$:

$\Pr[C_{\rho}(U_{n})=1]\leq 1000\cdot 2^{-(2^{\ell}-a)}\leq
2^{-(2^{\ell}-a-10)}.$

Finally, by the second item in Lemma 4.4 we have that with probability at
least $0.01$ over $\rho\leftarrow\mathsf{R}^{n}_{p}$:

$\Pr[C_{\rho}(U^{1/3}_{n})=1]\geq 0.01$

Overall, by a union bound with probability at least $1-(0.99+0.001+0.001)>0$
over $\rho\leftarrow\mathsf{R}^{n}_{p}$, we obtain a $\rho$ that satisfies all
three conditions. ∎

Let $\rho$ be the restriction guaranteed by the claim. We can view $C_{\rho}$
as $C_{\rho}=\bigvee_{\alpha\in\\{0,1\\}^{a}}C^{\alpha}_{\rho}$. This means
that $C_{\rho}$ is an OR of $2^{a}$ decision trees of height $a$. Each such
decision tree can be replaced by an $a$-DNF with $2^{a}$ clauses, and overall,
we get that $C_{\rho}$ is an $a$-DNF with $2^{2a}$ clauses. This gives that:

######  Claim 4.7.

If $q<\frac{1000}{\epsilon}$ then there exists an $a$-DNF $C^{\prime}$ with
$p\cdot n$ variables and $2^{2a}$ clauses such that:

  * •

$\Pr[C^{\prime}(U_{p\cdot n})=1]\leq 2^{-(2^{\ell}-a-10)}$.

  * •

$\Pr[C^{\prime}(U^{1/3}_{p\cdot n})=1]\geq 0.01$.

This means that one of the $2^{2a}$ clauses of $C^{\prime}$ must satisfy the
following:

######  Claim 4.8.

If $q<\frac{1000}{\epsilon}$ then there exists a DNF clause $\bar{C}$ over
$t\leq a$ literals such that:

  * •

$\Pr[\bar{C}(U_{t})=1]\leq 2^{-(2^{\ell}-a-10)}$.

  * •

$\Pr[\bar{C}(U^{1/3}_{t})=1]\geq\frac{0.01}{2^{2a}}\geq 2^{-(2a+10)}$.

We are now ready to prove Lemma 4.5. We assume for the purpose of
contradiction that $q<\frac{1000}{\epsilon}$ and show that Claim 4.8 yields a
contradiction. This is because a DNF clause over $t\leq a$ literals cannot
distinguish $U_{t}$ from $U^{1/3}_{t}$ with the parameters stated in Claim
4.8.

More precisely, as under $U^{1/3}_{t}$, every literal evaluates to one with
probability that is upper bounded by $2/3$, we conclude that:

$\Pr[\bar{C}(U^{1/3}_{t})=1]\leq\left(\frac{2}{3}\right)^{t}.$

Under $U_{t}$, every literal evaluates to one with probability half.
Therefore,

$\Pr[\bar{C}(U_{t})=1]=\left(\frac{1}{2}\right)^{t}.$

By Claim 4.8 it follows that:

$\left(\frac{4}{3}\right)^{t}=\frac{\left(\frac{2}{3}\right)^{t}}{\left(\frac{1}{2}\right)^{t}}\geq\frac{2^{-(2a+10)}}{2^{-(2^{\ell}-a-10)}}=2^{2^{\ell}-3a-20}.$

which gives that:

$a\geq t\geq\frac{2^{\ell}-3a-20}{\log\frac{4}{3}}>\frac{2^{\ell}}{10},$

using the assumption that $a\leq\frac{2^{\ell}}{10}$, and the lemma follows.

###  4.3 Proof of Theorem 4.2

In this section we prove Theorem 4.2. We first apply Lemma 4.3 and obtain that
for every $\alpha\in\\{0,1\\}^{a}$, there exists a $q$-CNF $C^{\alpha}$ with
$2^{q+\ell}$ clauses, over $n=2^{\ell^{\prime}}$ variables, such that for
$C=\bigvee_{\alpha\in\\{0,1\\}^{a}}C^{\alpha}$, we have that:

  * •

$\Pr[C(U_{n})=1]\leq 2^{-(2^{\ell}-a)}$.

  * •

For every $x\in\\{0,1\\}^{n}$ such that
$\operatorname{weight}(x)\leq(\frac{1}{2}-\epsilon)\cdot n$, there exists
$\alpha\in\\{0,1\\}^{a}$ such that $C^{\alpha}(x)=1$.

As there are $2^{a}$ such CNFs, it follows that one of them satisfies:

######  Claim 4.9.

There exists $\alpha\in\\{0,1\\}^{a}$ such that:

  * •

$\Pr[C^{\alpha}(U_{n})=1]\leq 2^{-(2^{\ell}-a)}$.

  * •

$\Pr[C^{\alpha}(U^{1/3}_{n})=1]\geq 2^{-(a+1)}$.

###### Proof.

The first item follows because the top gate of $C$ is an OR gate. For the
second item, by a Chernoff bound, and our assumption that
$\epsilon\leq\frac{1}{10}$:

$\Pr_{x\leftarrow
U^{1/3}_{n}}[\operatorname{weight}(x)\leq(\frac{1}{2}-\epsilon)\cdot n]\leq
2^{-\Omega(n)}\leq\frac{1}{2},$

meaning that:

$\Pr_{x\leftarrow U^{1/3}_{n}}[C(x)=1]\geq\frac{1}{2},$

and by averaging, there exists $\alpha\in\\{0,1\\}^{a}$ such that:

$\Pr_{x\leftarrow U^{1/3}_{n}}[C^{\alpha}(x)=1]\geq\frac{1}{2\cdot 2^{a}}.$

∎

Let $C_{0}=C^{\alpha}$ that is guaranteed by Claim 4.9. We will start from
$C_{0}$ and will iteratively apply the following lemma (which is proven in
Section 4.3.1).

######  Lemma 4.10.

For every $v$-CNF $D$ over $m$ variables, if $\Pr[D(U^{1/3}_{m})=1]\geq
2^{-w}$ then there exists a restriction $\rho:[m]\to\left\\{{0,1,*}\right\\}$
with $\operatorname{Free}(\rho)=m^{\prime}=m-w\cdot 4^{v}$, such that:

  * •

$D_{\rho}$ is a $(v-1)$-CNF over $m^{\prime}$ variables.

  * •

$\Pr[D_{\rho}(U_{m^{\prime}})=1]\leq\Pr[D(U_{m})=1]\cdot 2^{w\cdot 4^{v}}$.

  * •

$\Pr[D_{\rho}(U^{1/3}_{m^{\prime}})=1]\geq\Pr[D(U^{1/3}_{m})=1]$.

More precisely, at every step $i>0$, we apply Lemma 4.10 with $w=a+1$ on
$D=C_{i-1}$, and set $C_{i}=D_{\rho}$. We use $m_{i}$ to denote the input
length of $C_{i}$. We will maintain the following invariant (and note that
this indeed holds for $i=0$).

Invariant:

At step $i$ the following hold:

  * •

$C_{i}$ is a $(q-i)$-CNF.

  * •

$\Pr[C_{i}(U_{m_{i}})=1]\leq 2^{-\left(2^{\ell}-a-i\cdot(a+1)\cdot
4^{q}\right)}$.

  * •

$\Pr[C_{i}(U^{1/3}_{m_{i}})=1]\geq 2^{-(a+1)}$.

It immediately follows that this invariant holds for every $i\leq q$. This
means that at the conclusion of this process, for $i=q$ we have that:

  * •

$C_{m}$ is a constant.

  * •

$\Pr[C_{q}(U_{m_{q}})=1]\leq 2^{-\left(2^{\ell}-a-q\cdot(a+1)\cdot
4^{q}\right)}$.

  * •

$\Pr[C_{q}(U^{1/3}_{m_{q}})=1]\geq 2^{-(a+1)}$.

Therefore, by the third item, it must be that $C_{m}$ is the constant one, and
by the second item it must be that:

$2^{-\left(2^{\ell}-a-q\cdot(a+1)\cdot 4^{q}\right)}\geq 1.$

which implies that:

$q\geq\frac{\ell-\log(a+1)}{3}.$

####  4.3.1 Proof of Lemma 4.10

In this section, we prove Lemma 4.10. We first observe that if a $v$-CNF does
not have many clauses that have disjoint variables, then there must be a small
“cover” (namely, a set of variables such that each clause contains a variable
from the cover).

######  Proposition 4.11.

In every $v$-CNF $D$, if there does not exist $t$ clauses with disjoint
variables, then there is a subset $S$ of $s=(t-1)\cdot v$ variables, such that
every clause of $D$ contains a variable in $S$.

###### Proof.

We go over the clauses one by one, staring with an empty $S$. Every time the
current clause does not contain a variable from $S$, we mark the current
clause, and add its variables to $S$. Every time we mark a clause, its
variables are disjoint from all variables of previously marked clauses. By our
assumption, we mark at most $t-1$ clauses, and so when we conclude the size of
$S$ is at most $(t-1)\cdot v$. ∎

######  Lemma 4.12.

For every $v$-CNF $D$ over $m$ variables, if $\Pr[D(U^{1/3}_{m})=1]\geq
2^{-w}$ then there exists a set $S$ of size $s=w\cdot 4^{v}$ variables such
that every clause of $D$ contains at least one variable in $S$.

###### Proof.

If there does not exists a set $S$ with the required properties, then by
Proposition 4.11, $D$ has $t=\frac{s}{v}$ clauses that have disjoint
variables. Under $U^{1/3}_{m}$, each literal of $D$ has probability at least
$1/3$ to evaluate to zero. This gives that each clause has probability at most
$1-\left(\frac{1}{3}\right)^{v}$ to evaluate to one. Consequently, the
probability that $t$ disjoint clauses evaluate to one is at most
$\left(1-\left(\frac{1}{3}\right)^{v}\right)^{t}$, implying that:

$\Pr[D(U^{1/3}_{m})=1]\leq\left(1-\left(\frac{1}{3}\right)^{v}\right)^{t}\leq
e^{-3^{-v}\cdot t}<e^{-4^{-v}\cdot s}\leq 2^{-w}.$

and we get a contradiction. ∎

We are ready to prove Lemma 4.10. By Lemma 4.12 there exists a set $S$ of size
$s=w\cdot 4^{v}$ variables such that every clause of $D$ contains at least one
variable in $S$. Let $A$ be the set of all restrictions that fix the variables
in $S$, while leaving the other variables free. More precisely,

$A=\left\\{{\rho:[m]\to\left\\{{0,1,*}\right\\}:\rho(i)\neq*\mbox{ iff }i\in
S}\right\\}.$

We will show that there exists a $\rho\in A$ that satisfies the guarantees of
Lemma 4.10 with positive probability.

The first item of Lemma 4.10 holds for every $\rho\in A$. This is because
every clause of $D$ has a variable in $S$ and following the restriction, each
clause is over at most $v-1$ variables.

The second item of Lemma 4.10 also holds for every $\rho\in A$. For every
choice $y\in\\{0,1\\}^{w\cdot 4^{v}}$ of the restricted bits in $\rho$, let
$E_{\rho,y}$ denote the event
$\left\\{{X|_{[n]\setminus\operatorname{Select}(\rho)}=y}\right\\}$. For every
$\rho\in A$ we have that:

$\displaystyle\Pr[D_{\rho}[D(U_{m^{\prime}})=1]$
$\displaystyle=\Pr_{X\leftarrow U_{m}}[D(X)=1|E_{\rho,y}]$
$\displaystyle\leq\frac{\Pr_{X\leftarrow U_{m}}[D(X)=1]}{\Pr_{X\leftarrow
U_{m}}[E_{\rho,y}]}$ $\displaystyle=\Pr[D(U_{m})=1]\cdot 2^{w\cdot 4^{v}}.$

The third item follows because by averaging, there exists $\rho\in A$ and
$y\in\\{0,1\\}^{w\cdot 4^{v}}$ such that $\operatorname{Assign}(\rho)=y$ and:

$\Pr_{X\leftarrow U^{1/3}_{m}}[D(X)=1|E_{\rho,y}]\geq\Pr_{X\leftarrow
U^{1/3}_{m}}[D(X)=1],$

For this choice of $\rho$ and $y$, we have that

$\displaystyle\Pr[D_{\rho}(U^{1/3}_{m^{\prime}})=1]$
$\displaystyle=\Pr_{X\leftarrow U^{1/3}_{m}}[D(X)=1|X\in E_{\rho,y}]$
$\displaystyle\geq\Pr_{X\leftarrow U^{1/3}_{m}}[D(X)=1]$
$\displaystyle=\Pr[D(U^{1/3}_{m^{\prime}})=1].$

This concludes the proof of Lemma 4.10.

##  5 Improved lower bounds for local list-decoding algorithms

In this section we show that the techniques developed in Section 4 can be used
to get an improved lower bounds on the number of queries of local list-
decoding algorithms. In Section 5.1 we review the definition of locally list-
decodable codes, and local decoding algorithms. In Section 5.2 we state our
improved bound and compare it to previous work. In Section 5.3 we prove the
improved bound.

###  5.1 Definition of locally list-decodable codes

List-decodable codes are a natural extension of (uniquely decodable) error-
correcting codes, as it allows (list) decoding for error regimes where unique
decoding is impossible. This is an extensively studied area; see [Gur06] for a
survey. In this paper, we will be interested in list-decoding of binary codes.

######  Definition 5.1 (List-decodable code).

For a function $\operatorname{Enc}:\\{0,1\\}^{k}\rightarrow\\{0,1\\}^{n}$, and
$w\in\\{0,1\\}^{n}$, we define

$\operatorname{List}^{\operatorname{Enc}}_{\alpha}(w)=\left\\{{m\in\\{0,1\\}^{k}:\mathsf{dist}(\operatorname{Enc}(m),w)\leq\alpha}\right\\}.$

We say that $\operatorname{Enc}$ is $(\alpha,L)$-list-decodable if for every
$w\in\\{0,1\\}^{n}$,
$|\operatorname{List}^{\operatorname{Enc}}_{\alpha}(w)|\leq L$.

The task of _algorithmic_ list-decoding is to produce the list
$\operatorname{List}^{\operatorname{Enc}}_{\alpha}(w)$ on input
$w\in\\{0,1\\}^{n}$.

_Local_ unique decoding algorithms are algorithms that given an index
$i\in[k]$, make few oracle queries to $w$, and reproduce the bit $m_{i}$ (with
high probability over the choice of their random coins), where $m$ denotes the
unique codeword close to $w$. This notion of _local decoding_ has many
connections and applications in computer science and mathematics [Yek12].

We will be interested in _local_ list-decoding algorithms that receive oracle
access to a received word $w\in\\{0,1\\}^{n}$, as well as inputs $i\in[k]$ and
$j\in[L]$. We will require that for every
$m\in\operatorname{List}^{\operatorname{Enc}}_{\alpha}(w)$, with high
probability, there exists a $j\in[L]$ such that for every $i\in[k]$, when
$\operatorname{Dec}$ receives oracle access to $w$ and inputs $i,j$, it
produces $m_{i}$ with high probability over its choice of random coins. This
motivates the next definition.

######  Definition 5.2 (Randomized local computation).

We say that a procedure $P(i,r)$ locally computes a string $m\in\\{0,1\\}^{k}$
with error $\delta$, if for every $i\in[k]$, $\Pr[P(i,R)=m_{i}]\geq 1-\delta$
(where the probability is over a uniform choice of the “string of random
coins” $R$).

The definition of local list-decoders considers an algorithmic scenario that
works in two steps:

  * •

At the first step (which can be thought of as a preprocessing step) the local
list-decoder $\operatorname{Dec}$ is given oracle access to $w$ and an index
$j\in[L]$. It tosses random coins (which we denote by
$r^{\operatorname{shared}}$).

  * •

At the second step, the decoder receives the additional index $i\in[k]$, and
tosses additional coins $r$.

  * •

It is required that for every $w\in\\{0,1\\}^{n}$ and
$m\in\operatorname{List}^{\operatorname{Enc}}_{\alpha}(w)$, with probability
$2/3$ over the choice of the shared coins $r^{\operatorname{shared}}$, there
exists $j\in[L]$ such that when the local list-decoder receives $j$, it
locally computes $m$ (using its “non-shared” coins $r$). The definition uses
two types of random coins because the coins $r^{\operatorname{shared}}$ are
“shared” between different choices of $i\in[k]$ and allow different $i$’s to
“coordinate”. The coins $r$, are chosen independently for different choices of
$i\in[k]$.

This is formally stated in the next definition.

######  Definition 5.3 (Local list-decoder).

Let $\operatorname{Enc}:\\{0,1\\}^{k}\rightarrow\\{0,1\\}^{n}$ be a function.
An $(\alpha,L,q,\delta)$-local list-decoder (LLD) for $\operatorname{Enc}$ is
an oracle procedure $\operatorname{Dec}^{(\cdot)}$ that receives oracle access
to a word $w\in\\{0,1\\}^{n}$, and makes at most $q$ calls to the oracle. The
procedure $\operatorname{Dec}$ also receives inputs:

  * •

$i\in[k]$ : The index of the symbol that it needs to decode.

  * •

$j\in[L]$ : An index to the list.

  * •

Two strings $r^{\operatorname{shared}},r$ that are used as random coins.

It is required that for every $w\in\\{0,1\\}^{n}$, and for every
$m\in\operatorname{List}^{\operatorname{Enc}}_{\alpha}(w)$, with probability
at least $2/3$ over choosing a uniform string $r^{\operatorname{shared}}$,
there exists $j\in[L]$ such that the procedure

$P_{w,j,r^{\operatorname{shared}}}(i,r)=\operatorname{Dec}^{w}(i,j,r^{\operatorname{shared}},r)$