MCSP MFSP MKtP MKTP itrMCSP itrMKTP itrMINKT MINKT MINK MINcKT CMD DCMD CGL
PARITY Gap Empty Avoid Sparsification HammingEst HammingHit Circuit-Eval Hard
cHard CAPP GapUNSAT OV PRIMES PCP PCPP FMA Avg ZPEXP DLOGTIME ALOGTIME
ATIMESZKA Laconic- APEPP SAPEPP TFΣ NTIMEGUESS FZPP Formula THR MAJ DOR ETHR
Midbit LCS TAUT

# Symmetric Exponential Time Requires Near-Maximum Circuit Size

Lijie Chen
UC Berkeley
<EMAIL_ADDRESS>Shuichi Hirahara
National Institute of Informatics
<EMAIL_ADDRESS>Hanlin Ren
University of Oxford
<EMAIL_ADDRESS>
###### Abstract

We show that there is a language in $\S_{2}\E/_{1}$ (symmetric exponential
time with one bit of advice) with circuit complexity at least $2^{n}/n$. In
particular, the above also implies the same near-maximum circuit lower bounds
for the classes $\Sigma_{2}\E$, $(\Sigma_{2}\E\cap\Pi_{2}\E)/_{1}$, and
$\mathsf{ZPE}^{\NP}/_{1}$. Previously, only “half-exponential” circuit lower
bounds for these complexity classes were known, and the smallest complexity
class known to require exponential circuit complexity was
$\Delta_{3}\E=\E^{\Sigma_{2}\P}$ (Miltersen, Vinodchandran, and Watanabe
COCOON’99).

Our circuit lower bounds are corollaries of an unconditional zero-error
pseudodeterministic algorithm with an $\NP$ oracle and one bit of advice
($\FZPP^{\NP}/_{1}$) that solves the range avoidance problem infinitely often.
This algorithm also implies unconditional infinitely-often pseudodeterministic
$\FZPP^{\NP}/_{1}$ constructions for Ramsey graphs, rigid matrices, two-source
extractors, linear codes, and $\mathrm{K}^{\mathrm{poly}}$-random strings with
nearly optimal parameters.

Our proofs relativize. The two main technical ingredients are (1) Korten’s
$\P^{\NP}$ reduction from the range avoidance problem to constructing hard
truth tables (FOCS’21), which was in turn inspired by a result of Jeřábek on
provability in Bounded Arithmetic (Ann. Pure Appl. Log. 2004); and (2) the
recent iterative win-win paradigm of Chen, Lu, Oliveira, Ren, and Santhanam
(FOCS’23).

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results
    2. 1.2 Intuitions
    3. 1.3 Proof Overview
    4. 1.4 Discussions
  2. 2 Preliminaries
    1. 2.1 Complexity Classes
    2. 2.2 Single-valued $\mathsf{F}\Sigma_{2}\P$ and $\mathsf{F}\S_{2}\P$ Algorithms
    3. 2.3 The Range Avoidance Problem
  3. 3 Korten’s Reduction
    1. 3.1 GGM Tree and the Reduction
    2. 3.2 $\Pi_{1}$ Verification of the History of $\mathsf{Korten}(C,f)$
  4. 4 Circuit Lower Bounds for $\Sigma_{2}\E$
  5. 5 Circuit Lower Bounds for $\S_{2}\E$
    1. 5.1 Reed–Muller Codes
    2. 5.2 Encoded History and $\S_{2}\BPP$ Verification
    3. 5.3 Lower Bounds for $\S_{2}\E$
    4. 5.4 Infinitely Often Single-Valued $\mathsf{F}\S_{2}\P$ Algorithm for Arbitrary Input Range Avoidance

##  1 Introduction

Proving lower bounds against non-uniform computation (i.e., circuit lower
bounds) is one of the most important challenges in theoretical computer
science. From Shannon’s counting argument [Sha49, FM05], we know that almost
all $n$-bit Boolean functions have _near-maximum_ ($2^{n}/n$) circuit
complexity.111All $n$-input Boolean functions can be computed by a circuit of
size $(1+\frac{3\log n}{n}+O(\frac{1}{n}))2^{n}/n$ [Lup58, FM05], while most
Boolean functions require circuits of size $(1+\frac{\log
n}{n}-O(\frac{1}{n}))2^{n}/n$ [FM05]. Hence, in this paper, we say an $n$-bit
Boolean function has _near-maximum_ circuit complexity if its circuit
complexity is at least $2^{n}/n$. Therefore, the task of proving circuit lower
bounds is simply to _pinpoint_ one such hard function. More formally, one
fundamental question is:

> What is the smallest complexity class that contains a language of
> exponential ($2^{\Omega(n)}$) circuit complexity?

Compared with super-polynomial lower bounds, exponential lower bounds are
interesting in their own right for the following reasons. First, an
exponential lower bound would make Shannon’s argument _fully constructive_.
Second, exponential lower bounds have more applications than super-polynomial
lower bounds: For example, if one can show that $\E$ has no $2^{o(n)}$-size
circuits, then we would have $\text{pr}\P=\text{pr}\BPP$ [NW94, IW97], while
super-polynomial lower bounds such as $\EXP\not\subset\P/_{\mathrm{poly}}$
only imply sub-exponential time derandomization of pr.222$\E=\DTIME[2^{O(n)}]$
denotes _single-exponential_ time and $\EXP=\DTIME[2^{n^{O(1)}}]$ denotes
_exponential_ time; classes such as $\E^{\NP}$ and $\EXP^{\NP}$ are defined
analogously. Exponential time and single-exponential time are basically
interchangeable in the context of super-polynomial lower bounds (by a padding
argument); the exponential lower bounds proven in this paper will be stated
for single-exponential time classes since this makes our results stronger.
Below, $\Sigma_{3}\E$ and $\Pi_{3}\E$ denote the exponential-time versions of
$\Sigma_{3}\P=\NP^{\NP^{\NP}}$ and $\Pi_{3}\P=\coNP^{\NP^{\NP}}$,
respectively.

Unfortunately, despite its importance, our knowledge about exponential lower
bounds is quite limited. Kannan [Kan82] showed that there is a function in
$\Sigma_{3}\E\cap\Pi_{3}\E$ that requires maximum circuit complexity; the
complexity of the hard function was later improved to
$\Delta_{3}\E=\E^{\Sigma_{2}\P}$ by Miltersen, Vinodchandran, and Watanabe
[MVW99], via a simple binary search argument. This is essentially all we know
regarding exponential circuit lower bounds.333We also mention that Hirahara,
Lu, and Ren [HLR23] recently proved that for every constant $\varepsilon>0$,
$\BPE^{\MCSP}/_{2^{\varepsilon n}}$ requires near-maximum circuit complexity,
where $\MCSP$ is the Minimum Circuit Size Problem [KC00]. However, the hard
function they constructed requires subexponentially ($2^{\varepsilon n}$) many
advice bits to describe.

We remark that Kannan [Kan82, Theorem 4] claimed that
$\Sigma_{2}\E\cap\Pi_{2}\E$ requires exponential circuit complexity, but
[MVW99] pointed out a gap in Kannan’s proof, and suggested that exponential
lower bounds for $\Sigma_{2}\E\cap\Pi_{2}\E$ were “reopened and considered an
open problem.” Recently, Vyas and Williams [VW23] emphasized our lack of
knowledge regarding the circuit complexity of $\Sigma_{2}\EXP$, even with
respect to _relativizing_ proof techniques. In particular, the following
question has been open for at least 20 years (indeed, if we count from
[Kan82], it would be at least 40 years):

######  Open Problem 1.1.

Can we prove that $\Sigma_{2}\EXP\not\subset\SIZE[2^{\varepsilon n}]$ for some
absolute constant $\varepsilon>0$, or at least show a relativization barrier
for proving such a lower bound?

##### The half-exponential barrier.

There is a richer literature regarding super-polynomial lower bounds than
exponential lower bounds. Kannan [Kan82] proved that the class
$\Sigma_{2}\E\cap\Pi_{2}\E$ does not have polynomial-size circuits. Subsequent
works proved super-polynomial circuit lower bounds for exponential-time
complexity classes such as $\ZPEXP^{\NP}$ [KW98, BCG+96], $\S_{2}\EXP$
[CCHO05, Cai07], $\PEXP$ [Vin05, Aar06], and $\mathsf{MAEXP}$ [BFT98, San09].

Unfortunately, all these works fail to prove exponential lower bounds. All of
their proofs go through certain _Karp–Lipton_ collapses [KL80]; such a proof
strategy runs into a so-called “half-exponential barrier”, preventing us from
getting exponential lower bounds. See Section 1.4.1 for a detailed discussion.

###  1.1 Our Results

####  1.1.1 New near-maximum circuit lower bounds

In this work, we _overcome_ the half-exponential barrier mentioned above and
resolve 1.1 by showing that both $\Sigma_{2}\E$ and
$(\Sigma_{2}\E\cap\Pi_{2}\E)/_{1}$ require near-maximum ($2^{n}/n$) circuit
complexity. Moreover, our proof indeed _relativizes_ :

######  Theorem 1.2.

$\Sigma_{2}\E\not\subset\SIZE[2^{n}/n]$ and
$(\Sigma_{2}\E\cap\Pi_{2}\E)/_{1}\not\subset\SIZE[2^{n}/n]$. Moreover, they
hold in every relativized world.

Up to one bit of advice, we finally provide a proof of Kannan’s original claim
in [Kan82, Theorem 4]. Moreover, with some more work, we extend our lower
bounds to the smaller complexity class $\S_{2}\E/_{1}$ (see 2.1 for a formal
definition), again with a relativizing proof:

######  Theorem 1.3.

$\S_{2}\E/_{1}\not\subset\SIZE[2^{n}/n]$. Moreover, this holds in every
relativized world.

##### The symmetric time class $\S_{2}\E$.

$\S_{2}\E$ can be seen as a “randomized” version of $\E^{\NP}$ since it is
sandwiched between $\E^{\NP}$ and $\ZPE^{\NP}$: it is easy to show that
$\E^{\NP}\subseteq\S_{2}\E$ [RS98], and it is also known that
$\S_{2}\E\subseteq\ZPE^{\NP}$ [Cai07]. We also note that under plausible
derandomization assumptions (e.g., $\E^{\NP}$ requires $2^{\Omega(n)}$-size
$\SAT$-oracle circuits), all three classes simply collapse to $\E^{\NP}$
[KvM02].

Hence, our results also imply a near-maximum circuit lower bound for the class
$\ZPE^{\NP}/_{1}\subseteq(\Sigma_{2}\E\cap\Pi_{2}\E)/_{1}$. This vastly
improves the previous lower bound for $\Delta_{3}\E=\E^{\Sigma_{2}\P}$.

######  Corollary 1.4.

$\ZPE^{\NP}/_{1}\not\subset\SIZE[2^{n}/n]$. Moreover, this holds in every
relativized world.

####  1.1.2 New algorithms for the range avoidance problem

##### Background on $\Avoid$.

Actually, our circuit lower bounds are implied by our new algorithms for
solving the range avoidance problem ($\Avoid$) [KKMP21, Kor21, RSW22], which
is defined as follows: given a circuit $C:\\{0,1\\}^{n}\to\\{0,1\\}^{n+1}$ as
input, find a string outside the range of $C$ (we define
$\mathrm{Range}(C)\coloneqq\\{C(z):z\in\\{0,1\\}^{n}\\}$). That is, output any
string $y\in\\{0,1\\}^{n+1}$ such that for every $x\in\\{0,1\\}^{n}$,
$C(x)\neq y$.

There is a trivial $\FZPP^{\NP}$ algorithm solving $\Avoid$: randomly generate
strings $y\in\\{0,1\\}^{n+1}$ and output the first $y$ that is outside the
range of $C$ (note that we need an $\NP$ oracle to verify if
$y\notin\mathrm{Range}(C)$). The class $\APEPP$ (Abundant Polynomial Empty
Pigeonhole Principle) [KKMP21] is the class of total search problems reducible
to $\Avoid$.

As demonstrated by Korten [Kor21, Section 3], $\APEPP$ captures the complexity
of explicit construction problems whose solutions are guaranteed to exist by
the probabilistic method (more precisely, the dual weak pigeonhole principle
[Kra01, Jeř04]), in the sense that constructing such objects reduces to the
range avoidance problem. This includes many important objects in mathematics
and theoretical computer science, including Ramsey graphs [Erd59], rigid
matrices [Val77, GLW22, GGNS23], two-source extractors [CZ19, Li23], linear
codes [GLW22], hard truth tables [Kor21], and strings with maximum time-
bounded Kolmogorov complexity (i.e., $\mathrm{K}^{\mathrm{poly}}$-random
strings) [RSW22]. Hence, derandomizing the trivial $\FZPP^{\NP}$ algorithm for
$\Avoid$ would imply explicit constructions for all these important objects.

##### Our results: new pseudodeterministic algorithms for $\Avoid$.

We show that, _unconditionally_ , the trivial $\FZPP^{\NP}$ algorithm for
$\Avoid$ can be made _pseudodeterministic_ on infinitely many input lengths. A
_pseudodeterministic_ algorithm [GG11] is a randomized algorithm that outputs
the same _canonical_ answer on most computational paths. In particular, we
have:

######  Theorem 1.5.

For every constant $d\geq 1$, there is a randomized algorithm $\mathcal{A}$
with an $\NP$ oracle such that the following holds for infinitely many
integers $n$. For every circuit $C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{n+1}$ of
size at most $n^{d}$, there is a string
$y_{C}\in\\{0,1\\}^{n}\setminus\mathrm{Range}(C)$ such that $\mathcal{A}(C)$
either outputs $y_{C}$ or $\bot$, and the probability (over the internal
randomness of $\mathcal{A}$) that $\mathcal{A}(C)$ outputs $y_{C}$ is at least
$2/3$. Moreover, this theorem holds in every relativized world.

As a corollary, for every problem in $\APEPP$, we obtain zero-error
pseudodeterministic constructions with an $\NP$ oracle and one bit of advice
($\FZPP^{\NP}/_{1}$) that works infinitely often444The one-bit advice encodes
whether our algorithm succeeds on a given input length; it is needed since on
bad input lengths, our algorithm might not be pseudodeterministic (i.e., there
may not be a canonical answer that is outputted with high probability).:

######  Corollary 1.6 (Informal).

There are infinitely-often zero-error pseudodeterministic constructions for
the following objects with an $\NP$ oracle and one-bit of advice: Ramsey
graphs, rigid matrices, two-source extractors, linear codes, hard truth
tables, and $\mathrm{K}^{\mathrm{poly}}$-random strings.

Actually, we obtain single-valued $\mathsf{F}\S_{2}\P/_{1}$ algorithms for the
explicit construction problems above (see 2.2), and the pseudodeterministic
$\FZPP^{\NP}/_{1}$ algorithms follow from Cai’s theorem that
$\S_{2}\P\subseteq\ZPP^{\NP}$ [Cai07]. We stated them as pseudodeterministic
$\FZPP^{\NP}/_{1}$ algorithms since this notion is better known than the
notion of single-valued $\mathsf{F}\S_{2}\P/_{1}$ algorithms.

Theorem 1.5 is tantalizingly close to an infinitely-often $\FP^{\NP}$
algorithm for $\Avoid$ (with the only caveat of being _zero-error_ instead of
being completely _deterministic_). However, since an $\FP^{\NP}$ algorithm for
range avoidance would imply near-maximum circuit lower bounds for $\E^{\NP}$,
we expect that it would require fundamentally new ideas to completely
derandomize our algorithm. Previously, Hirahara, Lu, and Ren [HLR23, Theorem
36] presented an infinitely-often pseudodeterministic $\FZPP^{\NP}$ algorithm
for the range avoidance problem using $n^{\varepsilon}$ bits of advice, for
any small constant $\varepsilon>0$. Our result improves the above in two
aspects: first, we reduce the number of advice bits to $1$; second, our
techniques relativize but their techniques do not.

##### Lower bounds against non-uniform computation with maximum advice length.

Finally, our results also imply lower bounds against non-uniform computation
with maximum advice length. We mention this corollary because it is a stronger
statement than circuit lower bounds, and similar lower bounds appeared
recently in the literature of super-fast derandomization [CT21b].

######  Corollary 1.7.

For every $\alpha(n)\geq\omega(1)$ and any constant $k\geq 1$,
$\S_{2}\E/_{1}\not\subset\TIME[2^{kn}]/_{2^{n}-\alpha(n)}$. The same holds for
$\Sigma_{2}\E$, $(\Sigma_{2}\E\cap\Pi_{2}\E)/_{1}$, and $\ZPE^{\NP}/_{1}$ in
place of $\S_{2}\E/_{1}$. Moreover, this holds in every relativized world.

###  1.2 Intuitions

In the following, we present some high-level intuitions for our new circuit
lower bounds.

####  1.2.1 Perspective: single-valued constructions

A key perspective in this paper is to view circuit lower bounds (for
exponential-time classes) as _single-valued_ constructions of hard truth
tables. This perspective is folklore; it was also emphasized in recent papers
on the range avoidance problem [Kor21, RSW22].

Let $\Pi\subseteq\\{0,1\\}^{\star}$ be an _$\varepsilon$ -dense_ property,
i.e., for every integer $N\in\mathbb{N}$, $|\Pi_{N}|\geq\varepsilon\cdot
2^{N}$. (In what follows, we use $\Pi_{N}:=\Pi\cap\\{0,1\\}^{N}$ to denote the
length-$N$ slice of $\Pi$.) As a concrete example, let $\Pi_{\rm hard}$ be the
set of hard truth tables, i.e., a string $tt\in\Pi_{\rm hard}$ if and only if
it is the truth table of a function $f:\\{0,1\\}^{n}\to\\{0,1\\}$ whose
circuit complexity is at least $2^{n}/n$, where $n:=\log N$. (We assume that
$n:=\log N$ is an integer.) Shannon’s argument [Sha49, FM05] shows that
$\Pi_{\rm hard}$ is a $1/2$-dense property. We are interested in the following
question:

> What is the complexity of _single-valued_ constructions for any string in
> $\Pi_{\rm hard}$?

Here, informally speaking, a computation is _single-valued_ if each of its
computational paths either fails or outputs the _same_ value. For example, an
$\NP$ machine $M$ is a single-valued construction for $\Pi$ if there is a
“canonical” string $y\in\Pi$ such that (1) $M$ outputs $y$ on every accepting
computational path; (2) $M$ has at least one accepting computational path.
(That is, it is an $\mathsf{NPSV}$ construction in the sense of [BLS85,
FHOS93, Sel94, HNOS96].) Similarly, a $\BPP$ machine $M$ is a single-valued
construction for $\Pi$ if there is a “canonical” string $y\in\Pi$ such that
$M$ outputs $y$ on most (say $\geq 2/3$ fraction of) computational paths. (In
other words, single-valued $\ZPP$ and $\BPP$ constructions are another name
for _pseudodeterministic constructions_ [GG11].)555Note that the trivial
construction algorithms are not single-valued in general. For example, a
trivial $\Sigma_{2}\P=\NP^{\NP}$ construction algorithm for $\Pi_{\rm hard}$
is to guess a hard truth table $tt$ and use the $\NP$ oracle to verify that
$tt$ does not have size-$N/\log N$ circuits; however, different accepting
computational paths of this computation would output different hard truth
tables. Similarly, a trivial $\BPP$ construction algorithm for every dense
property $\Pi$ is to output a random string, but there is no _canonical_
answer that is outputted with high probability. In other words, these
construction algorithms do not _define_ anything; instead, a single-valued
construction algorithm should _define_ some particular string in $\Pi$.

Hence, the task of proving circuit lower bounds is equivalent to the task of
_defining_ , i.e., single-value constructing, a hard function, in the smallest
possible complexity class. For example, a single-valued $\BPP$ construction
(i.e., pseudodeterministic construction) for $\Pi_{\rm hard}$ is equivalent to
the circuit lower bound
$\BPE\not\subset\mathrm{i.o.}\text{-}\SIZE[2^{n}/n]$.666To see this, note that
(1) $\BPE\not\subset\mathrm{i.o.}\text{-}\SIZE[2^{n}/n]$ implies a simple
single-valued $\BPP$ construction for $\Pi_{\rm hard}$: given $N=2^{n}$,
output the truth table of $L_{n}$ ($L$ restricted to $n$-bit inputs), where
$L\in\BPE$ is the hard language not in $\SIZE[2^{n}/n]$; and (2) assuming a
single-valued $\BPP$ construction $A$ for $\Pi_{\rm hard}$, one can define a
hard language $L$ such that the truth table of $L_{n}$ is the output of
$A(1^{2^{n}})$, and observe that $L\in\BPE$. In this regard, the previous
near-maximum circuit lower bound for $\Delta_{3}\E:=\E^{\Sigma_{2}\P}$ [MVW99]
can be summarized in one sentence: The lexicographically first string in
$\Pi_{\rm hard}$ can be constructed in $\Delta_{3}\P:=\P^{\Sigma_{2}\P}$
(which is necessarily single-valued).

##### Reduction to $\Avoid$.

It was observed in [KKMP21, Kor21] that explicit construction of elements from
$\Pi_{\rm hard}$ is a special case of range avoidance: Let
$\mathsf{TT}\colon\\{0,1\\}^{N-1}\to\\{0,1\\}^{N}$ (here $N=2^{n}$) be a
circuit that maps the description of a $2^{n}/n$-size circuit into its
$2^{n}$-length truth table (by [FM05], this circuit can be encoded by $N-1$
bits). Hence, a single-valued algorithm solving $\Avoid$ for $\mathsf{TT}$ is
equivalent to a single-valued construction for $\Pi_{\rm hard}$. This explains
how our new range avoidance algorithms imply our new circuit lower bounds (as
mentioned in Section 1.1.2).

In the rest of Section 1.2, we will only consider the special case of $\Avoid$
where the input circuit for range avoidance is a $\P$-uniform circuit family.
Specifically, let
$\\{C_{n}\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}\\}_{n\in\mathbb{N}}$ be a
$\P$-uniform family of circuits, where $|C_{n}|\leq\mathrm{poly}(n)$.777We
assume that $C_{n}$ stretches $n$ bits to $2n$ bits instead of $n+1$ bits for
simplicity; Korten [Kor21] showed that there is a $\P^{\NP}$ reduction from
the range avoidance problem with stretch $n+1$ to the range avoidance problem
with stretch $2n$. Our goal is to find an algorithm $A$ such that for
infinitely many $n$,
$A(1^{n})\in\\{0,1\\}^{2n}\setminus\mathrm{Range}(C_{n})$; see Section 5.3 and
Section 5.4 for how to turn this into an algorithm that works for arbitrary
input circuit with a single bit of stretch. Also, since from now on we will
not talk about truth tables anymore, we will use $n$ instead of $N$ to denote
the input length of $\Avoid$ instances.

####  1.2.2 The iterative win-win paradigm of [CLO+23]

In a recent work, Chen, Lu, Oliveira, Ren, and Santhanam [CLO+23] introduced
the _iterative win-win_ paradigm for explicit constructions, and used that to
obtain a polynomial-time pseudodeterministic construction of primes that works
infinitely often. Since our construction algorithm closely follows their
paradigm, it is instructive to take a detour and give a high-level overview of
how the construction from [CLO+23] works.888Indeed, for every
$1/\mathrm{poly}(n)$-dense property $\Pi\in\P$, they obtained a polynomial-
time algorithm $A$ such that for infinitely many $n\in\mathbb{N}$, there
exists $y_{n}\in\Pi_{n}$ such that $A(1^{n})$ outputs $y_{n}$ with probability
at least $2/3$. By [AKS04] and the prime number theorem, the set of $n$-bit
primes is such a property.

In this paradigm, for a (starting) input length $n_{0}$ and some $t=O(\log
n_{0})$, we will consider an increasing sequence of input lengths
$n_{0},n_{1},\dotsc,n_{t}$ (jumping ahead, we will set $n_{i+1}=n_{i}^{\beta}$
for a large constant $\beta$), and show that our construction algorithm
succeeds on at least one of the input lengths. By varying $n_{0}$, we can
construct infinitely many such sequences of input lengths that are pairwise
disjoint, and therefore our algorithm succeeds on infinitely many input
lengths.

In more detail, fixing a sequence of input lengths $n_{0},n_{1},\dotsc,n_{t}$
and letting $\Pi$ be an $\varepsilon$-dense property, for each
$i\in\\{0,1,\dotsc,t\\}$, we specify a (deterministic) algorithm
$\mathsf{ALG}_{i}$ that takes $1^{n_{i}}$ as input and aims to construct an
explicit element from $\Pi_{n_{i}}$. We let $\mathsf{ALG}_{0}$ be the simple
brute-force algorithm that enumerates all length-$n_{0}$ strings and finds the
lexicographically first string in $\Pi_{n_{0}}$; it is easy to see that
$\mathsf{ALG}_{0}$ runs in $T_{0}:=2^{O(n_{0})}$ time.

##### The win-or-improve mechanism.

The core of [CLO+23] is a novel _win-or-improve mechanism_ , which is
described by a (randomized) algorithm $R$. Roughly speaking, for input lengths
$n_{i}$ and $n_{i+1}$, $R(1^{n_{i}})$ attempts to _simulate $\mathsf{ALG}_{i}$
faster by using the oracle $\Pi_{n_{i+1}}$_ (hence it runs in
$\mathrm{poly}(n_{i+1})$ time). The crucial property is the following win-win
argument:

  1. (Win)

Either $R(1^{n_{i}})$ outputs $\mathsf{ALG}_{i}(1^{n_{i}})$ with probability
at least $2/3$ over its internal randomness,

  2. (Improve)

or, from the failure of $R(1^{n_{i}})$, we can construct an algorithm
$\mathsf{ALG}_{i+1}$ that outputs an explicit element from $\Pi_{n_{i+1}}$ and
runs in $T_{i+1}=\mathrm{poly}(T_{i})$ time.

We call the above (Win-or-Improve), since either we have a pseudodeterministic
algorithm $R(1^{n_{i}})$ that constructs an explicit element from
$\Pi_{n_{i}}$ in $\mathrm{poly}(n_{i+1})\leq\mathrm{poly}(n_{i})$ time (since
it simulates $\mathsf{ALG}_{i}$), or we have an _improved_ algorithm
$\mathsf{ALG}_{i+1}$ at the input length $n_{i+1}$ (for example, on input
length $n_{1}$, the running time of $\mathsf{ALG}_{1}$ is
$2^{O\left(n_{1}^{1/\beta}\right)}\ll 2^{O(n_{1})}$). The (Win-or-Improve)
part in [CLO+23] is implemented via the Chen–Tell targeted hitting set
generator [CT21a] (we omit the details here). Jumping ahead, in this paper, we
will implement a similar mechanism using Korten’s $\P^{\NP}$ reduction from
the range avoidance problem to constructing hard truth tables [Kor21].

##### Getting polynomial time.

Now we briefly explain why (Win-or-Improve) implies a _polynomial-time_
construction algorithm. Let $\alpha$ be an absolute constant such that we
always have $T_{i+1}\leq T_{i}^{\alpha}$; we now set $\beta:=2\alpha$. Recall
that $n_{i}=n_{i-1}^{\beta}$ for every $i$. The crucial observation is the
following:

> Although $T_{0}$ is much larger than $n_{0}$, the sequence $\\{T_{i}\\}$
> grows slower than $\\{n_{i}\\}$.

Indeed, a simple calculation shows that when $t=O(\log n_{0})$, we will have
$T_{t}\leq\mathrm{poly}(n_{t})$; see [CLO+23, Section 1.3.1].

For each $0\leq i<t$, if $R(1^{n_{i}})$ successfully simulates
$\mathsf{ALG}_{i}$, then we obtain an algorithm for input length $n_{i}$
running in $\mathrm{poly}(n_{i+1})\leq\mathrm{poly}(n_{i})$ time. Otherwise,
we have an algorithm $\mathsf{ALG}_{i+1}$ running in $T_{i+1}$ time on input
length $n_{i+1}$. Eventually, we will hit $t$ such that
$T_{t}\leq\mathrm{poly}(n_{t})$, in which case $\mathsf{ALG}_{t}$ itself gives
a polynomial-time construction on input length $n_{t}$. Therefore, we obtain a
polynomial-time algorithm on at least one of the input lengths
$n_{0},n_{1},\dotsc,n_{t}$.

####  1.2.3 Algorithms for range-avoidance via Korten’s reduction

Now we are ready to describe our new algorithms for $\Avoid$. Roughly
speaking, our new algorithm makes use of the iterative win-win argument
introduced above, together with an easy-witness style argument [IKW02] and
Korten’s reduction [Kor21].999Korten’s result was inspired by [Jeř04], which
proved that the dual weak pigeonhole principle is equivalent to the statement
asserting the existence of Boolean functions with exponential circuit
complexity in a certain fragment of Bounded Arithmetic. In the following, we
introduce the latter two ingredients and show how to chain them together via
the iterative win-win argument.

##### An easy-witness style argument.

Let $\mathsf{BF}$ be the $2^{O(n)}$-time brute-force algorithm outputting the
lexicographically first non-output of $C_{n}$. Our first idea is to consider
its _computational history_ , a unique $2^{O(n)}$-length string $h_{\sf BF}$
(that can be computed in $2^{O(n)}$ time), and _branch on whether $h_{\sf BF}$
has a small circuit or not_. Suppose $h_{\sf BF}$ admits a, say,
$n^{\alpha}$-size circuit for some large $\alpha$, then we apply an _easy-
witness-style_ argument [IKW02] to simulate $\mathsf{BF}$ by a single-valued
$\mathsf{F}\Sigma_{2}\P$ algorithm running in
$\mathrm{poly}(n^{\alpha})=\mathrm{poly}(n)$ time (see Section 1.3.2). Hence,
we obtained the desired algorithm when $h_{\sf BF}$ is easy.

However, it is less clear how to deal with the other case (when $h_{\sf BF}$
is hard) directly. The crucial observation is that we have gained the
following ability: we can generate a string $h_{\sf
BF}\in\\{0,1\\}^{2^{O(n)}}$ that has circuit complexity at least $n^{\alpha}$,
in only $2^{O(n)}$ time.

##### Korten’s reduction.

We will apply Korten’s recent work [Kor21] to make use of the “gain” above. So
it is worth taking a detour to review the main result of [Kor21]. Roughly
speaking, [Kor21] gives an algorithm that uses a hard truth table $f$ to solve
a derandomization task: finding a non-output of the given circuit (that has
more output bits than input bits).101010This is very similar to the classical
hardness-vs-randomness connection [NW94, IW97], which can be understood as an
algorithm that uses a hard truth table $f$ (i.e., a truth table without small
circuits) to solve another derandomization task: estimating the acceptance
probability of the given circuit. This explains why one may want to use
Korten’s algorithm to replace the Chen–Tell targeted generator construction
[CT21a] from [CLO+23], as they are both hardness-vs-randomness connections.

Formally, [Kor21] gives a $\P^{\NP}$-computable algorithm
$\mathsf{Korten}(C,f)$ that takes as inputs a circuit
$C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}$ and a string $f\in\\{0,1\\}^{T}$
(think of $n\ll T$), and outputs a string $y\in\\{0,1\\}^{2n}$. The guarantee
is that if the circuit complexity of $f$ is sufficiently larger than the size
of $C$, then the output $y$ is not in the range of $C$.

This fits perfectly with our “gain” above: for $\beta\ll\alpha$ and
$m=n^{\beta}$, $\mathsf{Korten}(C_{m},h_{\sf BF})$ solves $\Avoid$ for $C_{m}$
since the circuit complexity of $h_{\sf BF}$, $n^{\alpha}$, is sufficiently
larger than the size of $C_{m}$. Moreover, $\mathsf{Korten}(C_{m},h_{\sf BF})$
runs in only $2^{O(n)}$ time, which is much less than the brute-force running
time $2^{O(m)}$. Therefore, we obtain an improved algorithm for $\Avoid$ on
input length $m$.

##### The iterative win-win argument.

What we described above is essentially the first stage of an _win-or-improve
mechanism_ similar to that from Section 1.2.2. Therefore, we only need to
iterate the argument above to obtain a polynomial-time algorithm.

For this purpose, we need to consider the computational history of not only
$\mathsf{BF}$, but also algorithms of the form
$\mathsf{Korten}(C,f)$.111111Actually, we need to consider all algorithms
$\mathsf{ALG}_{i}$ defined below and prove the properties of computational
history for these algorithms. It turns out that all of $\mathsf{ALG}_{i}$ are
of the form $\mathsf{Korten}(C,f)$ (including $\mathsf{ALG}_{0}$), so in what
follows we only consider the computational history of $\mathsf{Korten}(C,f)$.
For any circuit $C$ and “hard” truth table $f$, there is a _unique_
“computational history” $h$ of $\mathsf{Korten}(C,f)$, and the length of $h$
is upper bounded by $\mathrm{poly}(|f|)$. We are able to prove the following
statement akin to the _easy witness lemma_ [IKW02]: if $h$ admits a size-$s$
circuit (think of $s\ll T$), then $\mathsf{Korten}(C,f)$ can be simulated by a
single-valued $\mathsf{F}\Sigma_{2}\P$ algorithm in time $\mathrm{poly}(s)$;
see Section 1.3.2 for details on this argument.121212With an “encoded” version
of history and more effort, we are able to simulate $\mathsf{Korten}(C,f)$ by
a single-valued $\mathsf{F}\S_{2}\P$ algorithm in time $\mathrm{poly}(s)$, and
that is how our $\S_{2}\E$ lower bound is proved; see Section 1.3.3 for
details.

Now, following the iterative win-win paradigm of [CLO+23], for a (starting)
input length $n_{0}$ and some $t=O(\log n_{0})$, we consider an increasing
sequence of input lengths $n_{0},n_{1},\dotsc,n_{t}$, and show that our
algorithm $A$ succeeds on at least one of the input lengths (i.e.,
$A(1^{n_{i}})\in\\{0,1\\}^{2n_{i}}\setminus\mathrm{Range}(C_{n_{i}})$ for some
$i\in\\{0,1,\dotsc,t\\}$). For each $i\in\\{0,1,\dotsc,t\\}$, we specify an
algorithm $\mathsf{ALG}_{i}$ of the form $\mathsf{Korten}(C_{n_{i}},-)$ that
aims to solve $\Avoid$ for $C_{n_{i}}$; in other words, we specify a string
$f_{i}\in\\{0,1\\}^{T_{i}}$ for some $T_{i}$ and let
$\mathsf{ALG}_{i}:=\mathsf{Korten}(C_{n_{i}},f_{i})$.

The algorithm $\mathsf{ALG}_{0}$ is simply the brute force algorithm
$\mathsf{BF}$ at input length $n_{0}$. (A convenient observation is that we
can specify an exponentially long string $f_{0}\in\\{0,1\\}^{2^{O(n_{0})}}$ so
that $\mathsf{Korten}(C_{n_{0}},f_{0})$ is equivalent to
$\mathsf{BF}=\mathsf{ALG}_{0}$; see 3.4.) For each $0\leq i<t$, to specify
$\mathsf{ALG}_{i+1}$, let $f_{i+1}$ denote the history of the algorithm
$\mathsf{ALG}_{i}$, and consider the following win-or-improve mechanism.

  1. (Win)

If $f_{i+1}$ admits an $n_{i}^{\alpha}$-size circuit (for some large constant
$\alpha$), by our easy-witness argument, we can simulate $\mathsf{ALG}_{i}$ by
a $\mathrm{poly}(n_{i})$-time single-valued $\mathsf{F}\Sigma_{2}\P$
algorithm.

  2. (Improve)

Otherwise $f_{i+1}$ has circuit complexity at least $n_{i}^{\alpha}$, we plug
it into Korten’s reduction to solve $\Avoid$ for $C_{n_{i+1}}$. That is, we
take $\mathsf{ALG}_{i+1}\coloneqq\mathsf{Korten}(C_{n_{i+1}},f_{i+1})$ as our
new algorithm on input length $n_{i+1}$.

Let $T_{i}=|f_{i}|$, then $T_{i+1}\leq\mathrm{poly}(T_{i})$. By setting
$n_{i+1}=n_{i}^{\beta}$ for a sufficiently large $\beta$, a similar analysis
as [CLO+23] shows that for some $t=O(\log n_{0})$ we would have
$T_{t}\leq\mathrm{poly}(n_{t})$, meaning that $\mathsf{ALG}_{t}$ would be a
$\mathrm{poly}(n_{t})$-time $\FP^{\NP}$ algorithm (thus also a single-valued
$\mathsf{F}\Sigma_{2}\P$ algorithm) solving $\Avoid$ for $C_{n_{t}}$. Putting
everything together, we obtain a polynomial-time single-valued
$\mathsf{F}\Sigma_{2}\P$ algorithm that solves $\Avoid$ for at least one of
the $C_{n_{i}}$.

##### The hardness condenser perspective.

Below we present another perspective on the construction above which may help
the reader understand it better. In the following, we fix
$C_{n}\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}$ to be the truth table generator
$\mathsf{TT}_{n,2n}$ that maps an $n$-bit description of a $\log(2n)$-input
circuit into its length-$2n$ truth table. Hence, instead of solving $\Avoid$
in general, our goal here is simply _constructing hard truth tables_ (or
equivalently, proving circuit lower bounds).

We note that $\mathsf{Korten}(\mathsf{TT}_{n,2n},f)$ can then be interpreted
as a _hardness condenser_ [BS06]:131313A hardness condenser takes a long truth
table $f$ with certain hardness and outputs a shorter truth table with similar
hardness. Given a truth table $f\in\\{0,1\\}^{T}$ whose circuit complexity is
sufficiently larger than $n$, it outputs a length-$2n$ truth table that is
maximally hard (i.e., without $n/\log n$-size circuits). The win-or-improve
mechanism can be interpreted as an iterative application of this hardness
condenser.

At the stage $i$, we consider the algorithm
$\mathsf{ALG}_{i}\coloneqq\mathsf{Korten}(\mathsf{TT}_{n_{i},2n_{i}},f_{i})$,
which runs in $T_{i}\approx|f_{i}|$ time and creates (roughly) $n_{i}$ bits of
hardness. (That is, the circuit complexity of the output of $\mathsf{ALG}_{i}$
is roughly $n_{i}$.) In the (Win) case above, $\mathsf{ALG}_{i}$ admits an
$n_{i}^{\alpha}$-size history $f_{i+1}$ (with length approximately $|f_{i}|$)
and can therefore be simulated in $\mathsf{F}\Sigma_{2}\P$. The magic is that
in the (Improve) case, we actually have access to _much more hardness than
$n_{i}$_: the history string $f_{i+1}$ has $n_{i}^{\alpha}\gg n_{i}$ bits of
hardness. So we can _distill_ these hardness by applying the condenser to
$f_{i+1}$ to obtain a maximally hard truth tables of length
$2n_{i+1}=2n_{i}^{\beta}$, establish the next algorithm
$\mathsf{ALG}_{i+1}\coloneqq\mathsf{Korten}(\mathsf{TT}_{n_{i+1},2n_{i+1}},f_{i+1})$,
and keep iterating.

Observe that the string $f_{i+1}$ above has
$n_{i}^{\alpha}>n_{i}^{\beta}=n_{i+1}$ bits of hardness. Since
$|f_{i+1}|\approx|f_{i}|$ and $n_{i+1}=n_{i}^{\beta}$, the process above
creates _harder and harder_ strings, until $|f_{i+1}|\leq n_{i+1}\leq
n_{i}^{\alpha}$, so the (Win) case must happen at some point.

###  1.3 Proof Overview

In this section, we elaborate on the computational history of
$\mathsf{Korten}$ and how the easy-witness-style argument gives us
$\mathsf{F}\Sigma_{2}\P$ and $\mathsf{F}\S_{2}\P$ algorithms.

####  1.3.1 Korten’s reduction

We first review the key concepts and results from [Kor21] that are needed for
us. Given a circuit $C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}$ and a parameter
$T\geq 2n$, Korten builds another circuit $\mathsf{GGM}_{T}[C]$ stretching $n$
bits to $T$ bits as follows:141414We use the name $\mathsf{GGM}$ because the
construction is similar to the pseudorandom function generator of Goldreich,
Goldwasser, and Micali [GGM86].

  * •

On input $x\in\\{0,1\\}^{n}$, we set $v_{0,0}=x$. For simplicity, we assume
that $T/n=2^{k}$ for some $k\in\mathbb{N}$. We build a full binary tree with
$k+1$ layers; see Figure 1 for an example with $k=3$.

  * •

For every $i\in\\{0,1,\dotsc,k-1\\}$ and $j\in\\{0,1,\dotsc,2^{i}-1\\}$, we
set $v_{i+1,2j}$ and $v_{i+1,2j+1}$ to be the first $n$ bits and the last $n$
bits of $C(v_{i,j})$, respectively.

  * •

The output of $\mathsf{GGM}_{T}[C](x)$ is defined to be the concatenation of
$v_{k,0},v_{k,1},\dotsc,v_{k,2^{k}-1}$.

$v_{0,0}$$v_{1,0}$$v_{2,0}$$v_{3,0}$$v_{3,1}$$v_{2,1}$$v_{3,2}$$v_{3,3}$$v_{1,1}$$v_{2,2}$$v_{3,4}$$v_{3,5}$$v_{2,3}$$v_{3,6}$$v_{3,7}$
Figure 1: An illustration of the GGM Tree, in which, for instance, it holds
that $(v_{3,4},v_{3,5})=C(v_{2,2})$.

The following two properties of $\mathsf{GGM}_{T}[C]$ are established in
[Kor21], which will be useful for us:

  1. 1.

Given $i\in[T],C$ and $x\in\\{0,1\\}^{n}$, by traversing the tree from the
root towards the leaf with the $i$-th bit, one can compute the $i$-th bit of
$\mathsf{GGM}_{T}[C](x)$ in $\mathrm{poly}(\SIZE(C),\log T)$ time.
Consequently, for every $x$, $\mathsf{GGM}_{T}[C](x)$ has circuit complexity
at most $\mathrm{poly}(\SIZE(C),\log T)$.

  2. 2.

There is a $\P^{\NP}$ algorithm $\mathsf{Korten}(C,f)$ that takes an input
$f\in\\{0,1\\}^{T}\setminus\mathrm{Range}(\mathsf{GGM}_{T}[C])$ and outputs a
string $u\in\\{0,1\\}^{2n}\setminus\mathrm{Range}(C)$. Note that this is a
reduction from solving $\Avoid$ for $C$ to solving $\Avoid$ for
$\mathsf{GGM}_{T}[C]$.

In particular, letting $f$ be a truth table whose circuit complexity is
sufficiently larger than $\SIZE(C)$, by the first property above, it is not in
$\mathrm{Range}(\mathsf{GGM}_{T}[C])$, and therefore $\mathsf{Korten}(C,f)$
solves $\Avoid$ for $C$. This confirms our description of $\mathsf{Korten}$ in
Section 1.1.2.

####  1.3.2 Computational history of $\mathsf{Korten}$ and an easy-witness
argument for $\mathsf{F}\Sigma_{2}\P$ algorithms

The algorithm $\mathsf{Korten}(C,f)$ works as follows: we first view $f$ as
the labels of the last layer of the binary tree, and try to reconstruct the
whole binary tree, layer by layer (start from the bottom layer to the top
layer, within each layer, start from the rightmost node to the leftmost one),
by filling the labels of the intermediate nodes. To fill $v_{i,j}$, we use an
$\NP$ oracle to find the lexicographically first string $u\in\\{0,1\\}^{n}$
such that $C(u)=v_{i+1,2j}\circ v_{i+1,2j+1}$, and set $v_{i,j}=u$. If no such
$u$ exists, the algorithm stops and report $v_{i+1,2j}\circ v_{i+1,2j+1}$ as
the solution to $\Avoid$ for $C$. Observe that this reconstruction procedure
must stop somewhere, since if it successfully reproduces all the labels in the
binary tree, we would have
$f=\mathsf{GGM}_{T}[C](v_{0,0})\in\mathrm{Range}(\mathsf{GGM}_{T}[C])$,
contradicting the assumption. See 3.3 for details.

##### The computational history of $\mathsf{Korten}$.

The algorithm described above induces a natural description of the
computational history of $\mathsf{Korten}$, denoted as
$\mathsf{History}(C,f)$, as follows: the index $(i_{\star},j_{\star})$ when
the algorithm stops (i.e., the algorithm fails to fill in
$v_{i_{\star},j_{\star}}$) concatenated with the labels of all the nodes
generated by $\mathsf{Korten}(C,f)$ (for the intermediate nodes with no label
assigned, we set their labels to a special symbol $\bot$); see Figure 2 for an
illustration. This history has length at most $5T$, and for convenience, we
pad additional zeros at the end of it so that its length is exactly $5T$.

$\bot$$\bot$$\bot$$v_{3,0}$$v_{3,1}$$\bot$$v_{3,2}$$v_{3,3}$$\bot$$v_{2,2}$$v_{3,4}$$v_{3,5}$$v_{2,3}$$v_{3,6}$$v_{3,7}$$(i_{\star},j_{\star})=(2,1)$
Figure 2: An illustration of the history of $\mathsf{Korten}(C,f)$. Here we
have $\mathsf{History}(C,f)=(2,1)\circ\bot\bot\bot\bot\bot\circ v_{2,2}\circ
v_{2,3}\circ v_{3,0}\circ\dotsc\circ v_{3,7}$ and
$\mathsf{Korten}(C,f)=v_{3,2}\circ v_{3,3}$.

##### A local characterization of $\mathsf{History}(C,f)$.

The crucial observation we make on $\mathsf{History}(C,f)$ is that it admits a
local characterization in the following sense: there is a family of local
constraints $\\{\psi_{x}\\}_{x\in\\{0,1\\}^{\mathrm{poly}(n)}}$, where each
$\psi_{x}\colon\\{0,1\\}^{5T}\times\\{0,1\\}^{T}\to\\{0,1\\}$ reads only
$\mathrm{poly}(n)$ many bits of its input (we think about it as a local
constraint since usually $n\ll T$), such that for fixed $f$,
$\mathsf{History}(C,f)\circ f$ is the unique string making all the $\psi_{x}$
outputting $1$.

The constraints are follows: (1) for every leaf node $v_{k,i}$, its content is
consistent with the corresponding block in $f$; (2) all labels at or before
node $(i_{\star},j_{\star})$ are $\bot$;151515We say that $(i,j)$ is before
(after) $(i_{\star},j_{\star})$ if the pair $(i,j)$ is lexicographically
smaller (greater) than $(i_{\star},j_{\star})$. (3) for every
$z\in\\{0,1\\}^{n}$, $C(z)\neq v_{i_{\star}+1,2j_{\star}}\circ
v_{i_{\star}+1,2j_{\star}+1}$ (meaning the algorithm fails at
$v_{i_{\star},j_{\star}}$); (4) for every $(i,j)$ after
$(i_{\star},j_{\star})$, $C(v_{i,j})=v_{i+1,2j}\circ v_{i+1,2j+1}$ ($v_{i,j}$
is the correct label); (5) for every $(i,j)$ after $(i_{\star},j_{\star})$ and
for every $v^{\prime}<v_{i,j}$, $C(v^{\prime})\neq v_{i+1,2j}\circ
v_{i+1,2j+1}$ ($v_{i,j}$ is the lexicographically first correct label). It is
clear that each of these constraints above only reads $\mathrm{poly}(n)$ many
bits from the input and a careful examination shows they precisely define the
string $\mathsf{History}(C,f)$.

A more intuitive way to look at these local constraints is to treat them as a
$\mathrm{poly}(n)$-time oracle algorithm $V_{\mathsf{History}}$ that takes a
string $x\in\mathrm{poly}(n)$ as input and two strings $h\in\\{0,1\\}^{5T}$
and $f\in\\{0,1\\}^{T}$ as oracles, and we simply let
$V_{\mathsf{History}}^{h,f}(x)=\psi_{x}(h\circ f)$. Since the constraints
above are all very simple and only read $\mathrm{poly}(n)$ bits of $h\circ f$,
$V_{\mathsf{History}}$ runs in $\mathrm{poly}(n)$ time. In some sense,
$V_{\mathsf{History}}$ is a local $\Pi_{1}$ verifier: it is local in the sense
that it only queries $\mathrm{poly}(n)$ bits from its oracles, and it is
$\Pi_{1}$ since it needs a universal quantifier over
$x\in\\{0,1\\}^{\mathrm{poly}(n)}$ to perform all the checks.

#####  $\mathsf{F}\Sigma_{2}\P$ algorithms.

Before we proceed, we give a formal definition of a single-valued
$\mathsf{F}\Sigma_{2}\P$ algorithm $A$. Here $A$ is implemented by an
algorithm $V_{A}$ taking an input $x$ and two $\mathrm{poly}(|x|)$-length
witnesses $\pi_{1}$ and $\pi_{2}$. We say $A(x)$ outputs a string
$z\in\\{0,1\\}^{\ell}$ (we assume $\ell=\ell(x)$ can be computed in polynomial
time from $x$) if $z$ is the _unique_ length-$\ell$ string such that the
following hold:

  * •

there exists $\pi_{1}$ such that for every $\pi_{2}$,
$V_{\mathsf{History}}(x,\pi_{1},\pi_{2},z)=1$.161616Note that our definition
here is different from the formal definition we used in 2.2. But from this
definition, it is easier to see why $\mathsf{F}\Sigma_{2}\P$ algorithms for
constructing hard truth tables imply circuit lower bounds for $\Sigma_{2}\E$.

We can view $V_{\mathsf{History}}$ as a verifier that checks whether $z$ is
the desired output using another universal quantifier: given a proof $\pi_{1}$
and a string $z\in\\{0,1\\}^{\ell}$. $A$ accepts $z$ if and only if _for
every_ $\pi_{2}$, $V_{\mathsf{History}}(x,\pi_{1},\pi_{2},z)=1$. That is, $A$
can perform exponentially many checks on $\pi_{1}$ and $z$, each taking
$\mathrm{poly}(|x|)$ time.

##### The easy-witness argument.

Now we are ready to elaborate on the easy-witness argument mentioned in
Section 1.1.2. Recall that at stage $i$, we have
$\mathsf{ALG}_{i}=\mathsf{Korten}(C_{n_{i}},f_{i})$ and
$f_{i+1}=\mathsf{History}(C_{n_{i}},f_{i})$ (the history of
$\mathsf{ALG}_{i}$). Assuming that $f_{i+1}$ admits a
$\mathrm{poly}(n_{i})$-size circuit, we want to show that
$\mathsf{Korten}(C_{n_{i}},f_{i})$ can be simulated by a
$\mathrm{poly}(n_{i})$-time single-valued $\mathsf{F}\Sigma_{2}\P$ algorithm.

Observe that for every $t\in[i+1]$, $f_{t-1}$ is simply a substring of $f_{t}$
since $f_{t}=\mathsf{History}(C_{n_{t-1}},f_{t-1})$. Therefore, $f_{i+1}$
admitting a $\mathrm{poly}(n_{i})$-size circuit implies that all $f_{t}$ admit
$\mathrm{poly}(n_{i})$-size circuits for $t\in[i]$. We can then implement $A$
as follows: the proof $\pi_{1}$ is a $\mathrm{poly}(n_{i})$-size circuit
$C_{i+1}$ supposed to compute $f_{i+1}$, from which one can obtain in
polynomial time a sequence of circuits $C_{1},\dotsc,C_{i}$ that are supposed
to compute $f_{1},\dotsc,f_{i}$, respectively. (Also, from 3.4, one can easily
construct a $\mathrm{poly}(n_{0})$-size circuit $C_{0}$ computing $f_{0}$.)
Next, for every $t\in\\{0,1,\dotsc,i\\}$, $A$ checks whether
$\mathtt{tt}(C_{t+1})\circ\mathtt{tt}(C_{t})$ satisfies all the local
constraints $\psi_{x}$’s from the characterization of
$\mathsf{History}(C_{n_{t}},f_{t})$. In other words, $A$ checks whether
$V_{\mathsf{History}}^{C_{t+1},C_{t}}(x)=1$ for all
$x\in\\{0,1\\}^{\mathrm{poly}(n_{t})}$.

The crucial observation is that since all the $C_{t}$ have size
$\mathrm{poly}(n_{i})$, each check above can be implemented in
$\mathrm{poly}(n_{i})$ time as they only read at most $\mathrm{poly}(n_{i})$
bits from their input, despite that
$\mathtt{tt}(C_{t+1})\circ\mathtt{tt}(C_{t})$ itself can be much longer than
$\mathrm{poly}(n_{i})$. Assuming that all the checks of $A$ above are passed,
by induction we know that $f_{t+1}=\mathsf{History}(C_{n_{t}},f_{t})$ for
every $t\in\\{0,1,\dotsc,i\\}$. Finally, $A$ checks whether $z$ corresponds to
the answer described in $\mathtt{tt}(C_{i+1})=f_{i+1}$.

####  1.3.3 Selectors and an easy-witness argument for $\mathsf{F}\S_{2}\P$
algorithms

Finally, we discuss how to implement the easy-witness argument above with a
single-valued $\mathsf{F}\S_{2}\P$ algorithm. It is known that any single-
valued $\mathsf{F}\S_{2}\BPP$ algorithm can be converted into an equivalent
single-valued $\mathsf{F}\S_{2}\P$ algorithm outputting the same string
[Can96, RS98] (see also the proof of Theorem 5.7 for a self-contained
argument). Therefore, in the following we aim to give a single-valued
$\mathsf{F}\S_{2}\BPP$ algorithm for solving range avoidance, which is easier
to achieve.

#####  $\mathsf{F}\S_{2}\BPP$ algorithms and randomized selectors.

Before we proceed, we give a formal definition of a single-valued
$\mathsf{F}\S_{2}\BPP$ algorithm $A$. We implement $A$ by a randomized
algorithm $V_{A}$ that takes an input $x$ and two $\mathrm{poly}(|x|)$-length
witnesses $\pi_{1}$ and $\pi_{2}$.171717$\mathsf{F}\S_{2}\P$ algorithms are
the special case of $\mathsf{F}\S_{2}\BPP$ algorithms where the algorithm
$V_{A}$ is _deterministic_. We say that $A(x)$ outputs a string
$z\in\\{0,1\\}^{\ell}$ (we assume $\ell=\ell(x)$ can be computed in polynomial
time from $x$) if the following hold:

  * •

there exists a string $h$ such that for every $\pi$, both $V_{A}(x,h,\pi)$ and
$V_{A}(x,\pi,h)$ output $z$ with probability at least $2/3$. (Note that such
$z$ must be unique if it exists.)

Actually, our algorithm $A$ will be implemented as a randomized _selector_ :
given two potential proofs $\pi_{1}$ and $\pi_{2}$, it first selects the
correct one and then outputs the string $z$ induced by the correct
proof.181818If both proofs are correct or neither proofs are correct, it can
select an arbitrary one. The condition only applies when exactly one of the
proofs is correct.

##### Recap.

Revising the algorithm in Section 1.2.3, our goal now is to give an
$\mathsf{F}\S_{2}\BPP$ simulation of $\mathsf{Korten}(C_{n_{i}},f_{i})$,
assuming that $\mathsf{History}(C_{n_{i}},f_{i})$ admits a small circuit.
Similar to the local $\Pi_{1}$ verifier used in the case of
$\mathsf{F}\Sigma_{2}\P$ algorithms, now we consider a local randomized
selector $V_{\mathsf{select}}$ which takes oracles
$\pi_{1},\pi_{2}\in\\{0,1\\}^{5T}$ and $f\in\\{0,1\\}^{T}$ such that if
exactly one of the $\pi_{1}$ and $\pi_{2}$ is $\mathsf{History}(C,f)$,
$V_{\mathsf{select}}$ outputs its index with high probability.

Assuming that $f_{i+1}=\mathsf{History}(C_{n_{i}},f_{i})$ admits a small
circuit, one can similarly turn $V_{\mathsf{select}}$ into a single-valued
$\mathsf{F}\S_{2}\BPP$ algorithms $A$ computing
$\mathsf{Korten}(C_{n_{i}},f_{i})$: treat two proofs $\pi_{1}$ and $\pi_{2}$
as two small circuits $C$ and $D$ both supposed to compute $f_{i+1}$, from $C$
and $D$ we can obtain a sequence of circuits $\\{C_{t}\\}$ and $\\{D_{t}\\}$
supposed to compute the $f_{t}$ for $t\in[i]$. Then we can use the selector
$V_{\mathsf{select}}$ to decide for each $t\in[i+1]$ which of the $C_{t}$ and
$D_{t}$ is the correct circuit for $f_{t}$. Finally, we output the answer
encoded in the selected circuit for $f_{i+1}$; see the proof of Theorem 5.7
for details.191919However, for the reasons to be explained below, we will
actually work with the encoded history instead of the history, which entails a
lot of technical challenges in the actual proof.

##### Observation: it suffices to find the first differing node label.

Ignore the $(i_{\star},j_{\star})$ part of the history for now. Let
$\\{v^{1}_{i,j}\\}$ and $\\{v^{2}_{i,j}\\}$ be the node labels encoded in
$\pi_{1}$ and $\pi_{2}$, respectively. We also assume that exactly one of them
corresponds to the correct node labels in $\mathsf{History}(C,f)$. The crucial
observation here is that, since the correct node labels are generated by a
deterministic procedure _node by node_ (from bottom to top and from rightmost
to leftmost), it is possible to tell which of the $\\{v^{1}_{i,j}\\}$ and
$\\{v^{2}_{i,j}\\}$ is correct given the largest $(i^{\prime},j^{\prime})$
such that $v^{1}_{i^{\prime},j^{\prime}}\neq v^{2}_{i^{\prime},j^{\prime}}$.
(Note that since all $(i,j)$ are processed by $\mathsf{Korten}(C,f)$ in
reverse lexicographic order, this $(i^{\prime},j^{\prime})$ corresponds to the
first node label that the wrong process differs from the correct process, so
we call this the first differing point.)

In more detail, assuming we know this $(i^{\prime},j^{\prime})$, we proceed by
discussing several cases. First of all, if $(i^{\prime},j^{\prime})$
corresponds to a leaf, then one can query $f$ to figure out which of
$v^{1}_{i^{\prime},j^{\prime}}$ and $v^{2}_{i^{\prime},j^{\prime}}$ is
consistent with the corresponding block in $f$. Now we can assume
$(i^{\prime},j^{\prime})$ corresponds to an intermediate node. Since
$(i^{\prime},j^{\prime})$ is the first differing point, we know that
$v^{1}_{i^{\prime}+1,2j^{\prime}}\circ
v^{1}_{i^{\prime}+1,2j^{\prime}+1}=v^{2}_{i^{\prime}+1,2j^{\prime}}\circ
v^{2}_{i^{\prime}+1,2j^{\prime}+1}$ (we let this string to be $\alpha$ for
convenience). By the definition of $\mathsf{History}(C,f)$, it follows that
the correct $v_{i^{\prime},j^{\prime}}$ should be uniquely determined by
$\alpha$, which means the selector only needs to read $\alpha$,
$v^{1}_{i^{\prime},j^{\prime}}$, and $v^{2}_{i^{\prime},j^{\prime}}$, and can
then be implemented by a somewhat tedious case analysis (so it is local). We
refer readers to the proof of 5.5 for the details and only highlight the most
illuminating case here: if both of $v^{1}_{i^{\prime},j^{\prime}}$ and
$v^{2}_{i^{\prime},j^{\prime}}$ are good (we say a string $\gamma$ is good, if
$\gamma\neq\bot$ and $C(\gamma)=\alpha$), we select the lexicographically
smaller one. To handle the $(i_{\star},j_{\star})$ part, one needs some
additional case analysis. We omit the details here and refer the reader to the
proof of 5.5.

The takeaway here is that if we can find the first differing label
$(i^{\prime},j^{\prime})$, then we can construct the selector
$V_{\mathsf{select}}$ and hence the desired single-valued
$\mathsf{F}\S_{2}\BPP$ algorithm.

##### Encoded history.

However, the above assumes the knowledge of $(i^{\prime},j^{\prime})$. In
general, if one is only given oracle access to $\\{v^{1}_{i,j}\\}$ and
$\\{v^{2}_{i,j}\\}$, there is no $\mathrm{poly}(n)$-time oracle algorithm
computing $(i^{\prime},j^{\prime})$ because there might be exponentially many
nodes. To resolve this issue, we will encode $\\{v^{1}_{i,j}\\}$ and
$\\{v^{2}_{i,j}\\}$ via Reed–Muller codes.

Formally, recall that $\mathsf{History}(C,f)$ is the concatenation of
$(i_{\star},j_{\star})$ and the string $S$, where $S$ is the concatenation of
all the labels on the binary tree. We now define the encoded history, denoted
as $\widetilde{\mathsf{History}}(C,f)$, as the concatenation of
$(i_{\star},j_{\star})$ and _a Reed–Muller encoding_ of $S$. The new selector
is given oracle access to two candidate encoded histories together with $f$.
By applying low-degree tests and self-correction of polynomials, we can assume
that the Reed–Muller parts of the two candidates are indeed low-degree
polynomials. Then we can use a reduction to polynomial identity testing to
compute the first differing point between $\\{v^{1}_{i,j}\\}$ and
$\\{v^{2}_{i,j}\\}$ in randomized polynomial time. See the proof of 5.3 for
the details. This part is similar to the selector construction from [Hir15].

###  1.4 Discussions

We conclude the introduction by discussing some related works.

####  1.4.1 Previous approach: Karp–Lipton collapses and the half-exponential
barrier

In the following, we elaborate on the half-exponential barrier mentioned
earlier in the introduction.202020A function $f\colon\mathbb{N}\to\mathbb{N}$
is _sub-half-exponential_ if $f(f(n)^{c})=2^{o(n)}$ for every constant $c\geq
1$, i.e., composing $f$ twice yields a sub-exponential function. For example,
for constants $c\geq 1$ and $\varepsilon>0$, the functions $f(n)=n^{c}$ and
$f(n)=2^{\log^{c}n}$ are sub-half-exponential, but the functions
$f(n)=2^{n^{\varepsilon}}$ and $f(n)=2^{\varepsilon n}$ are not. Let
$\mathcal{C}$ be a “typical” uniform complexity class containing $\P$, a
_Karp–Lipton collapse_ to $\mathcal{C}$ states that if a large class (say
$\EXP$) has polynomial-size circuits, then this class collapses to
$\mathcal{C}$. For example, there is a Karp–Lipton collapse to
$\mathcal{C}=\Sigma_{2}\P$:

> Suppose $\EXP\subseteq\P/_{\mathrm{poly}}$, then $\EXP=\Sigma_{2}\P$.
> ([KL80], attributed to Albert Meyer)

Now, assuming that $\EXP\subseteq\P/_{\mathrm{poly}}\implies\EXP=\mathcal{C}$,
the following win-win analysis implies that $\mathcal{C}\text{-}\EXP$, the
exponential-time version of $\mathcal{C}$, is not in $\P/_{\mathrm{poly}}$:
(1) if $\EXP\not\subset\P/_{\mathrm{poly}}$, then of course
$\mathcal{C}\text{-}\EXP\supseteq\EXP$ does not have polynomial-size circuits;
(2) otherwise $\EXP\subseteq\P/_{\mathrm{poly}}$. We have $\EXP=\mathcal{C}$
and by padding $\EEXP=\mathcal{C}\text{-}\EXP$. Since $\EEXP$ contains a
function of maximum circuit complexity by direct diagonalization, it follows
that $\mathcal{C}\text{-}\EXP$ does not have polynomial-size circuits.

Karp–Lipton collapses are known for the classes $\Sigma_{2}\P$ [KL80],
$\ZPP^{\NP}$ [BCG+96], $\S_{2}\P$ [Cai07] (attributed to Samik Sengupta),
$\PP$, $\MA$ [LFKN92, BFNW93], and $\ZPP^{\MCSP}$ [IKV18]. All the
aforementioned super-polynomial circuit lower bounds for $\Sigma_{2}\EXP$,
$\ZPEXP^{\NP}$, $\S_{2}\EXP$, $\PEXP$, $\mathsf{MAEXP}$, and $\ZPEXP^{\MCSP}$
are proven in this way.212121There are some evidences that Karp–Lipton
collapses are essential for proving circuit lower bounds [CMMW19].

##### The half-exponential barrier.

The above argument is very successful at proving various super-polynomial
lower bounds. However, a closer look shows that it is only capable of proving
_sub-half-exponential_ circuit lower bounds. Indeed, suppose we want to show
that $\mathcal{C}\text{-}\EXP$ does not have circuits of size $f(n)$. We will
have to perform the following win-win analysis:

  * •

if $\EXP\not\subset\SIZE[f(n)]$, then of course
$\mathcal{C}\text{-}\EXP\supseteq\EXP$ does not have circuits of size $f(n)$;

  * •

if $\EXP\subseteq\SIZE[f(n)]$, then (a scaled-up version of) the Karp–Lipton
collapse implies that $\EXP$ can be computed by a $\mathcal{C}$ machine of
$\mathrm{poly}(f(n))$ time. Note that $\TIME[2^{\mathrm{poly}(f(n))}]$ does
not have circuits of size $f(n)$ by direct diagonalization. By padding,
$\TIME[2^{\mathrm{poly}(f(n))}]$ can be computed by a $\mathcal{C}$ machine of
$\mathrm{poly}(f(\mathrm{poly}(f(n))))$ time. Therefore, if $f$ is sub-half-
exponential (meaning $f(\mathrm{poly}(f(n)))=2^{o(n)}$), then
$\mathcal{C}\text{-}\EXP$ does not have circuits of size $f(n)$.

Intuitively speaking, the two cases above are _competing with each other_ : we
cannot get exponential lower bounds in both cases.

####  1.4.2 Implications for the Missing-String problem?

In the Missing-String problem, we are given a list of $m$ strings
$x_{1},x_{2},\dots,x_{m}\in\\{0,1\\}^{n}$ where $m<2^{n}$, and the goal is to
output any length-$n$ string $y$ that does not appear in
$\\{x_{1},x_{2},\dots,x_{m}\\}$. Vyas and Williams [VW23] connected the
circuit complexity of Missing-String with the (relativized) circuit complexity
of $\Sigma_{2}\E$:

######  Theorem 1.8 ([VW23, Theorem 32], Informal).

The following are equivalent:

  * •

$\Sigma_{2}\E^{A}\not\subset\mathrm{i.o.}\text{-}\SIZE^{A}[2^{\Omega(n)}]$ for
every oracle $A$;

  * •

for $m=2^{\Omega(n)}$, the Missing-String problem can be solved by a uniform
family of size-$2^{O(n)}$ depth-$3$ $\AC^{0}$ circuits.

The intuition behind Theorem 1.8 is roughly as follows. For every oracle $A$,
the set of truth tables with low $A$-oracle circuit complexity induces an
instance for Missing-String, and solving this instance gives us a hard truth
table relative to $A$. If the algorithm for Missing-String is a uniform
$\AC^{0}$ circuit of depth $3$, then the hard function is inside
$\Sigma_{2}\E^{A}$.

However, despite our Theorem 1.2 being completely relativizing, it does not
seem to imply any non-trivial depth-$3$ $\AC^{0}$ circuit for Missing-String.
The reason is the heavy win-win analysis _across multiple input lengths_ : for
each $0\leq i<t$, we have a single-valued $\mathsf{F}\Sigma_{2}\P$
construction algorithm for hard truth tables relative to oracle $A$ on input
length $n_{i}$, but this algorithm needs access to $A_{n_{i+1}}$, _a higher
input length of $A$_. Translating this into the language of Missing-String, we
obtain a weird-looking depth-$3$ $\AC^{0}$ circuit that takes as input a
_sequence_ of Missing-String instances
$\mathcal{I}_{n_{0}},\mathcal{I}_{n_{1}},\dots,\mathcal{I}_{n_{t}}$ (where
_each_ $\mathcal{I}_{n_{i}}\subseteq\\{0,1\\}^{n_{i}}$ is a set of strings),
looks at all of the instances (or, at least $\mathcal{I}_{n_{i}}$ and
$\mathcal{I}_{n_{i+1}}$), and outputs a purportedly missing string of
$\mathcal{I}_{n_{i}}$. It is guaranteed that for at least one input length
$i$, the output string is indeed a missing string of $\mathcal{I}_{n_{i}}$.
However, if our algorithm is only given one instance
$\mathcal{I}\subseteq\\{0,1\\}^{n}$, without assistance from a larger input
length, it does not know how to find any missing string of $\mathcal{I}$.

It remains an intriguing open problem whether the bullets in Theorem 1.8 are
true or not. In other words, is there an oracle $A$ relative to which
$\Sigma_{2}\E$ has small circuits _on infinitely many input lengths_?

## Organization

In Section 2, we introduce the necessary technical preliminaries for this
paper. In Section 3, we review Korten’s reduction from solving range avoidance
to generating hard truth tables [Kor21], together with some new properties
required by our new results. In Section 4, we prove the near-maximum circuit
lower bound for $\Sigma_{2}\E$; although this lower bound is superseded by the
later $\S_{2}\E/_{1}$ lower bound, we nonetheless include it in the paper
since its proof is much more elementary. In Section 5, we extend the near-
maximum circuit lower bound to $\S_{2}\E/_{1}$, and also present our new
algorithms for solving the range avoidance problem.

##  2 Preliminaries

##### Notation.

We use $[n]$ to denote $\\{1,2,\dots,n\\}$. A search problem $\Pi$ maps every
input $x\in\\{0,1\\}^{*}$ into a solution set $\Pi_{x}\subseteq\\{0,1\\}^{*}$.
We say an algorithm $A$ solves the search problem $\Pi$ on input $x$ if
$A(x)\in\Pi_{x}$.

###  2.1 Complexity Classes

We assume basic familiarity with computation complexity theory (see, e.g.,
[AB09, Gol08] for references). Below we recall the definition of
$\S_{2}\TIME[T(n)]$ [RS98, Can96].

######  Definition 2.1.

Let $T\colon\mathbb{N}\to\mathbb{N}$. We say a language
$L\in\S_{2}\TIME[T(n)]$, if there exists an $O(T(n))$-time verifier
$V(x,\pi_{1},\pi_{2})$ that takes $x\in\\{0,1\\}^{n}$ and
$\pi_{1},\pi_{2}\in\\{0,1\\}^{T(n)}$ as input, satisfying that

  * •

if $x\in L$, then there exists $\pi_{1}$ such that for every $\pi_{2}$,
$V(x,\pi_{1},\pi_{2})=1$, and

  * •

if $x\not\in L$, then there exists $\pi_{2}$ such that for every $\pi_{1}$,
$V(x,\pi_{1},\pi_{2})=0$.

Moreover, we say $L\in\S_{2}\E$ if $L\in\S_{2}\TIME[T(n)]$ for some $T(n)\leq
2^{O(n)}$, and $L\in\S_{2}\P$ if $L\in\S_{2}\TIME[p(n)]$ for some polynomial
$p$.

It is known that $\S_{2}\P$ contains $\MA$ and $\P^{\NP}$ [RS98], and
$\S_{2}\P$ is contained in $\ZPP^{\NP}$ [Cai07]. From its definition, it is
also clear that $\S_{2}\P\subseteq\Sigma_{2}\P\cap\Pi_{2}\P$.

###  2.2 Single-valued $\mathsf{F}\Sigma_{2}\P$ and $\mathsf{F}\S_{2}\P$
Algorithms

We consider the following definitions of single-valued algorithms which
correspond to circuit lower bounds for $\Sigma_{2}\E$ and $\S_{2}\E$.

######  Definition 2.2 (Single-valued $\mathsf{F}\Sigma_{2}\P$ and
$\mathsf{F}\S_{2}\P$ algorithms).

A single-valued $\mathsf{F}\Sigma_{2}\P$ algorithm $A$ is specified by a
polynomial $\ell(\cdot)$ together with a polynomial-time algorithm
$V_{A}(x,\pi_{1},\pi_{2})$. On an input $x\in\\{0,1\\}^{*}$, we say that $A$
outputs $y_{x}\in\\{0,1\\}^{*}$, if the following hold:

  1. (a)

There is a $\pi_{1}\in\\{0,1\\}^{\ell(|x|)}$ such that for every
$\pi_{2}\in\\{0,1\\}^{\ell(|x|)}$, $V_{A}(x,\pi_{1},\pi_{2})$ outputs $y_{x}$.

  2. (b)

For every $\pi_{1}\in\\{0,1\\}^{\ell(|x|)}$, there is a
$\pi_{2}\in\\{0,1\\}^{\ell(|x|)}$ such that the output of
$V_{A}(x,\pi_{1},\pi_{2})$ is either $y_{x}$ or $\bot$ (where $\bot$ indicates
“I don’t know”).

A single-valued $\mathsf{F}\S_{2}\P$ algorithm $A$ is specified similarly,
except that we replace the second condition above with the following:

  1. (b’)

There is a $\pi_{2}\in\\{0,1\\}^{\ell(|x|)}$ such that for every
$\pi_{1}\in\\{0,1\\}^{\ell(|x|)}$, $V_{A}(x,\pi_{1},\pi_{2})$ outputs $y_{x}$.

Now, we say that a single-valued $\mathsf{F}\Sigma_{2}\P$
($\mathsf{F}\S_{2}\P$) algorithm $A$ solves a search problem $\Pi$ on input
$x$ if it outputs a string $y_{x}$ and $y_{x}\in\Pi_{x}$. Note that from 2.2,
if $A$ outputs a string $y_{x}$, then $y_{x}$ is unique.

For convenience, we mostly only consider single-valued algorithms $A(x)$ with
fixed output lengths, meaning that the output length $|A(x)|$ only depends on
$|x|$ and can be computed in polynomial time given $1^{|x|}$.222222If $A$
takes multiple inputs like $x,y,z$, then the output length $A(x,y,z)$ only
depends on $|x|,|y|,|z|$ and can be computed in polynomial time given
$1^{|x|}$, $1^{|y|}$, and $1^{|z|}$.

####  2.2.1 Single-Valued $\mathsf{F}\S_{2}\P$ and $\mathsf{F}\Sigma_{2}\P$
algorithms with $\FP^{\NP}$ post-processing

We also need the fact that single-valued $\mathsf{F}\S_{2}\P$ or
$\mathsf{F}\Sigma_{2}\P$ algorithms with $\FP^{\NP}$ post-processing can still
be implemented by single-valued $\mathsf{F}\S_{2}\P$ or
$\mathsf{F}\Sigma_{2}\P$ algorithms, respectively. More specifically, we have:

######  Theorem 2.3.

Let $A(x)$ be a single-valued $\mathsf{F}\S_{2}\P$ (resp.
$\mathsf{F}\Sigma_{2}\P$) algorithm and $B(x,y)$ be an $\FP^{\NP}$ algorithm,
both with fixed output length. The function $f(x)\coloneqq B(x,A(x))$ also
admits an $\mathsf{F}\S_{2}\P$ (resp. $\mathsf{F}\Sigma_{2}\P$) algorithm.

###### Proof.

We only provide a proof for the case of single-valued $\mathsf{F}\S_{2}\P$
algorithms. Recall that the Lexicographically Maximum Satisfying Assignment
problem ($\mathsf{LMSAP}$) is defined as follows: given an $n$-variable
formula $\phi$ together with an integer $k\in[n]$, one needs to decide whether
$a_{k}=1$, where $a_{1},\dotsc,a_{n}\in\\{0,1\\}^{n}$ is the lexicographically
largest assignment satisfies $\phi$. By [Kre88], $\mathsf{LMSAP}$ is
$\P^{\NP}$-complete.

Let $V_{A}(x,\pi_{1},\pi_{2})$ be the corresponding verifier for the single-
valued $\mathsf{F}\S_{2}\P$ algorithm $A$. Let $L(x,y,i)$ be the $\P^{\NP}$
language such that $L(x,y,i)=1$ if and only if $B(x,y)_{i}=1$. Let
$\ell=|B(x,y)|$ be the output length of $B$. We now define a single-valued
$\mathsf{F}\S_{2}\P$ algorithm $\widetilde{A}$ by defining the following
verifier $V_{\widetilde{A}}$, and argue that $\widetilde{A}$ computes $f$.

The verifier $V_{\widetilde{A}}$ takes an input $x$ and two proofs
$\vec{\pi}_{1}$ and $\vec{\pi}_{2}$, where $\vec{\pi}_{1}$ consists of
$\omega_{1}$, acting as the second argument to $V_{A}$, and $\ell$ assignments
$z^{1}_{1},z^{1}_{2},\dotsc,z^{1}_{\ell}\in\\{0,1\\}^{m}$. Similarly,
$\vec{\pi}_{2}$ consists of $\omega_{2}$ and
$z^{2}_{1},z^{2}_{2},\dotsc,z^{2}_{\ell}\in\\{0,1\\}^{m}$.

First, $V_{\widetilde{A}}$ runs $V_{A}(x,\omega_{1},\omega_{2})$ to get
$y\in\\{0,1\\}^{|A(x)|}$. Then it runs the reduction from $L(x,y,i)$ to
$\mathsf{LMSAP}$ for every $i\in[\ell]$ to obtain $\ell$ instances
$\\{(\phi_{i},k_{i})\\}_{i\in[\ell]}$, where $\phi_{i}$ is an $m$-variable
formula and $k_{i}\in[m]$. (Without loss of generality by padding dummy
variables, we may assume that the number of variables in $\phi_{i}$ is the
same for each $i$, i.e., $m$; and that $m$ only depends on $|x|$ and $|y|$.)
Now, for every $\mu\in[2]$, we can define an answer
$w_{\mu}\in\\{0,1\\}^{\ell}$ by $(w_{\mu})_{i}=(z^{\mu}_{i})_{k_{i}}$ (i.e.,
the value of $B(x,y)$, assuming that $\vec{\pi}_{\mu}$ consists of the
lexicographically largest assignments for all the $\mathsf{LMSAP}$ instances).

In what follows, when we say that $V_{\widetilde{A}}$ _selects_ the proof
$\mu\in[2]$, we mean that $V_{\widetilde{A}}$ outputs $w_{\mu}$ and
terminates. Then, $V_{\widetilde{A}}$ works as follows:

  1. 1.

For each $\mu\in[2]$, it first checks whether for every $i\in[\ell]$,
$z^{\mu}_{i}$ satisfies $\phi_{i}$. If only one of the $\mu$ passes all the
checks, $V_{\widetilde{A}}$ selects that $\mu$. If none of them passes all the
checks, $V_{\widetilde{A}}$ selects $1$. Otherwise, it continues to the next
step.

  2. 2.

Now, letting $Z^{\mu}=z^{\mu}_{1}\circ z^{\mu}_{2}\circ\dotsc\circ
z^{\mu}_{\ell}$ for each $\mu\in[2]$. $V_{\widetilde{A}}$ selects the $\mu$
with the lexicographically larger $Z^{\mu}$. If $Z^{1}=Z^{2}$, then
$V_{\widetilde{A}}$ selects $1$.

Now we claim that $\widetilde{A}$ computes $f(x)$, which can be established by
setting $\vec{\pi}_{1}$ or $\vec{\pi}_{2}$ be the corresponding proof for
$V_{A}$ concatenated with all lexicographically largest assignments for the
$\\{\phi_{i}\\}_{i\in[\ell]}$. ∎

###  2.3 The Range Avoidance Problem

The _range avoidance_ problem [KKMP21, Kor21, RSW22] is the following problem:
Given as input a circuit $C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{\ell}$ where
$\ell>n$, find any string $y\in\\{0,1\\}^{\ell}\setminus\mathrm{Range}(C)$.
Proving circuit lower bounds (for exponential-time classes) is equivalent to
solving the range avoidance problem on the _truth table generator_
$\mathsf{TT}_{n,s}$, defined as follows. It was shown in [FM05] that for
$n,s\in\mathbb{N}$, any $s$-size $n$-input circuit $C$ can be encoded as a
_stack program_ with description size $L_{n,s}:=(s+1)(7+\log(n+s))$. The
precise definition of stack programs does not matter (see [FM05] for a formal
definition); the only property we need is that given $s$ and $n$ such that
$n\leq s\leq 2^{n}$, in $\mathrm{poly}(2^{n})$ time one can construct a
circuit $\mathsf{TT}_{n,s}\colon\\{0,1\\}^{L_{n,s}}\to\\{0,1\\}^{2^{n}}$
mapping the description of a stack program into its truth table. By the
equivalence between stack programs and circuits, it follows that any
$f\in\\{0,1\\}^{2^{n}}\setminus\mathrm{Range}(\mathsf{TT}_{n,s})$ satisfies
$\SIZE(f)>s$. Also, we note that for large enough $n\in\mathbb{N}$ and
$s=2^{n}/n$, we have $L_{n,s}<2^{n}$.

######  Fact 2.4.

Let $s(n)\colon\mathbb{N}\to\mathbb{N}$. Suppose that there is a single-valued
$\mathsf{F}\S_{2}\P$ algorithm $A$ such that for infinitely many
$n\in\mathbb{N}$, $A(1^{2^{n}})$ takes $\alpha(n)$ bits of advice and outputs
a string
$f_{n}\in\\{0,1\\}^{2^{n}}\setminus\mathrm{Range}(\mathsf{TT}_{n,s(n)})$. Then
$\S_{2}\E/_{\alpha(n)}\not\subset\SIZE[s(n)]$.

###### Proof sketch.

We define a language $L$ such that the truth table of the characteristic
function of $L\cap\\{0,1\\}^{n}$ is $A(1^{2^{n}})$. It is easy to see that
$L\notin\SIZE[s(n)]$ and $L\in\S_{2}\E/_{\alpha(n)}$. ∎

##  3 Korten’s Reduction

Our results crucially rely on a reduction in [Kor21] showing that proving
circuit lower bounds is “the hardest explicit construction” under $\P^{\NP}$
reductions.

##### Notation.

Let $s$ be a string of length $n$. We will always use $0$-index (i.e., the
first bit of $s$ is $s_{0}$ and the last bit of $s$ is $s_{n-1}$). Let $i<j$,
we use $s_{[i,j]}$ to denote the substring of $s$ from the $i$-th bit to the
$j$-th bit, and $s_{[i,j)}$ to denote the substring of $s$ from the $i$-th bit
to the $(j-1)$-th bit. (Actually, we will use the notation $s_{[i,j)}$ more
often than $s_{[i,j]}$ as it is convenient when we describe the GGM tree.) We
also use $s_{1}\circ s_{2}\circ\dots\circ s_{k}$ to denote the concatenation
of $k$ strings.

###  3.1 GGM Tree and the Reduction

We first recall the GGM tree construction from [GGM86], which is used in a
crucial way by [Kor21].

######  Definition 3.1 (The GGM tree construction [GGM86]).

Let $C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}$ be a circuit. Let
$n,T\in\mathbb{N}$ be such that $T\geq 4n$ and let $k$ be the smallest integer
such that $2^{k}n\geq T$. The function
$\mathsf{GGM}_{T}[C]\colon\\{0,1\\}^{n}\to\\{0,1\\}^{T}$ is defined as
follows.

Consider a perfect binary tree with $2^{k}$ leaves, where the root is on level
$0$ and the leaves are on level $k$. Each node is assigned a binary string of
length $n$, and for $0\leq j<2^{i}$, denote $v_{i,j}\in\\{0,1\\}^{n}$ the
value assigned to the $j$-th node on level $i$. Let $x\in\\{0,1\\}^{n}$. We
perform the following computation to obtain $\mathsf{GGM}_{T}[C](x)$: we set
$v_{0,0}:=x$, and for each $0\leq i<k$, $0\leq j<2^{i}$, we set
$v_{i+1,2j}:=C(v_{i,j})_{[0,n)}$ (i.e., the first half of $C(v_{i,j})$) and
$v_{i+1,2j+1}:=C(v_{i,j})_{[n,2n)}$ (i.e., the second half of $C(v_{i,j})$).
(We say the nodes $(i+1,2j)$ and $(i+1,2j+1)$ are “children” of $(i,j)$.)

Finally, we concatenate all values of the leaves and take the first $T$ bits
as the output:

$\mathsf{GGM}_{T}[C](x):=(v_{k,0}\circ v_{k,1}\circ\dots\circ
v_{k,2^{k}-1})_{[0,T)}.$

######  Lemma 3.2 (The output of GGM tree has a small circuit).

Let $\mathsf{GGMEval}(C,T,x,i)$ denote the $i$-th bit of
$\mathsf{GGM}_{T}[C](x)$. There is an algorithm running in
$\widetilde{O}\left(|C|\cdot\log T\right)$ time that, given $C,T,x,i$, outputs
$\mathsf{GGMEval}(C,T,x,i)$.

###### Proof Sketch.

We first note that to compute the $i$-th bit of
$\mathsf{GGM}_{T}[C](x):=(v_{k,0}\circ v_{k,1}\circ\dots\circ
v_{k,2^{k}-1})_{[0,T)}$, it suffices to compute $v_{k,\lfloor i/n\rfloor}$.
Computing $v_{k,\lfloor i/n\rfloor}$ can be done by descending from the root
of the GGM tree to the leave $(k,\lfloor i/n\rfloor)$, which takes
$\widetilde{O}(|C|\cdot\log T)$ time. ∎

It is shown in [Kor21] that the range avoidance problem for $C$ reduces to the
range avoidance problem for $\mathsf{GGM}_{T}[C]$. In what follows, we review
this proof, during which we also define the _computational history_ of
“solving range avoidance of $C$ from $\mathsf{GGM}_{T}[C]$”, which will be
crucial in our main proof.

1

Input: $C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}$ denotes the input circuit, and
$f\in\\{0,1\\}^{T}\setminus\mathrm{Range}(\mathsf{GGM}_{T}[C])$ denotes the
input “hard” truth table

Output: A non-output of $C$

Data: The computational history of $\mathsf{Korten}(C,f)$: a pair
$(i_{\star},j_{\star})$ and an array $\\{v_{i,j}\\}_{i,j}$ where
$i\in\\{0,1\dotsc,k\\}$ and $j\in\\{0,1,\dotsc,2^{i}\\}$.

2 Let $k\leftarrow\left\lceil\log_{2}(T/n)\right\rceil$;

3 Append $f$ with $2^{k}n-|f|$ zeros at the end;

4 for  _$j\leftarrow 0$ _to_ $2^{k}-1$_ do

5 $v_{k,j}\leftarrow f_{[jn,(j+1)n)}$;

/* the $j$-th ‘‘block’’ of $f$ */

6

7for  _$i\leftarrow k-1$ _downto_ $0$_ do

8 for  _$j\leftarrow 2^{i}-1$ _downto_ $0$_ do

9 Let $v_{i,j}$ be the lexicographically smallest string in
$C^{-1}(v_{i+1,2j}\circ v_{i+1,2j+1})$;

/* Note that this step needs to invoke the $\NP$ oracle */

10 if  _$v_{i,j}$ _does not exist__ then

11 For every $(i^{\prime},j^{\prime})$ such that $v_{i^{\prime},j^{\prime}}$
is not set yet, set $v_{i^{\prime},j^{\prime}}\leftarrow\bot$;

12 Set $i_{\star}:=i$, and $j_{\star}:=j$;

13 return $v_{i+1,2j}\circ v_{i+1,2j+1}$;

14

15

16

return _$\bot$_

Algorithm 3.1 $\mathsf{Korten}(C,f)$: Korten’s reduction

######  Lemma 3.3 (Reduction from solving range avoidance of $C$ to solving
range avoidance of $\mathsf{GGM}_{T}[C]$).

Let $C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}$ be a circuit. Let $f$ be a non-
output of $\mathsf{GGM}_{T}[C]$, i.e.,
$f\in\\{0,1\\}^{T}\setminus\mathrm{Range}(\mathsf{GGM}_{T}[C])$. Then,
$\mathsf{Korten}(C,f)$ (as defined in Algorithm 3.1) outputs a non-output of
$C$ in deterministic $\mathrm{poly}(T,n)$ time with an $\NP$ oracle.

###### Proof Sketch.

The running time of $\mathsf{Korten}(C,f)$ follows directly from its
description. Also, note that whenever $\mathsf{Korten}(C,f)$ outputs a string
$v_{i+1,2j}\circ v_{i+1,2j+1}\in\\{0,1\\}^{2n}$, it holds that this string is
not in the range of $C$. Therefore, it suffices to show that when
$f\in\\{0,1\\}^{T}\setminus\mathrm{Range}(\mathsf{GGM}_{T}[C])$,
$\mathsf{Korten}(C,f)$ does not return $\bot$.

Assume, towards a contradiction, that $\mathsf{Korten}(C,f)$ returns $\bot$.
This means that all the $\\{v_{i,j}\\}_{i,j}$ values are set. It follows from
the algorithm description that $f=\mathsf{GGM}_{T}[C](v_{0,0})$, which
contradicts the assumption that
$f\in\\{0,1\\}^{T}\setminus\mathrm{Range}(\mathsf{GGM}_{T}[C])$. ∎

In addition, we observe the following trivial fact:

######  Fact 3.4.

Let $C:\\{0,1\\}^{n}\to\\{0,1\\}^{2n}$ be a circuit, $T:=2^{2n}\cdot 2n$, and
$f$ be the concatenation of all length-$2n$ strings (which has length $T$).
Then $f\not\in\mathrm{Range}(\mathsf{GGM}_{T}[C])$.

One can combine 3.4 with 3.3 to obtain a brute force algorithm that solves the
range avoidance problem in $2^{O(n)}$ time with an $\NP$ oracle. Essentially,
this brute force algorithm tests every possible length-$2n$ string against the
range of the circuit. It will be the basis of our win-win analysis in Section
4.

Finally, we give the following remark, showing that Korten’s reduction
relativizes.

######  Remark 3.5.

Algorithm 3.1 and 3.3 _relativizes_ , in the sense that if the input is
actually an oracle circuit $C^{O}$ for some arbitrary oracle, the algorithm
still works except now it needs to call an $\NP^{O}$ oracle to find the
lexicographically smallest string in $C^{-1}(v_{i+1,2j}\circ v_{i+1,2j+1})$.

###  3.2 $\Pi_{1}$ Verification of the History of $\mathsf{Korten}(C,f)$

In what follows, we say that $(i,j)<(i^{\prime},j^{\prime})$ if either
$i<i^{\prime}$ or ($i=i^{\prime}$ and $j<j^{\prime}$) (that is, we consider
the lexicographical order of pairs). Observe that Algorithm 3.1 processes all
the pairs $(i,j)$ in the reverse lexicographic order.

######  Definition 3.6 (The computational history of $\mathsf{Korten}(C,f)$).

Let $n,T\in\mathbb{N}$ be such that $\log T\leq n\leq T$. Let
$C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}$ be a circuit, and $f\in\\{0,1\\}^{T}$
be a “hard truth table” in the sense that
$f\not\in\mathrm{Range}(\mathsf{GGM}_{T}[C])$. The _computational history_ of
$\mathsf{Korten}(C,f)$, denoted as

$\mathsf{History}(C,f),$

consists of $(i_{\star},j_{\star})$, as well as the concatenation of $v_{i,j}$
for every $0\leq i<k$ and $0\leq j<2^{i}$, in the lexicographical order of
$(i,j)$ ($(i_{\star},j_{\star})$ and the $v_{i,j}$ are defined in Algorithm
3.1). Each $v_{i,j}$ is encoded by $n+1$ bits ${\sf enc}(v_{i,j})$, where if
$v_{i,j}\in\\{0,1\\}^{n}$ then ${\sf enc}(v_{i,j})=0\circ v_{i,j}$, and if
$v_{i,j}=\bot$ then ${\sf enc}(v_{i,j})=1^{n+1}$. The length of this history
is at most $(2^{k+1}-1)(n+1)+2\log T\leq 5T$, and for convenience we always
pad zeros at the end so that its length becomes exactly $5T$.

The following lemma summarizes the properties of the computational history
construction above required for the $\Sigma_{2}\E$ lower bound in the next
section.

######  Lemma 3.7.

Let $n,T\in\mathbb{N}$ be such that $\log T\leq n\leq T$. Let
$C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}$ be a circuit and
$f\in\\{0,1\\}^{T}\setminus\mathrm{Range}(\mathsf{GGM}_{T}[C])$. Let
$h\coloneqq\mathsf{History}(C,f)$ and $z\coloneqq\mathsf{Korten}(C,f)$.

  1. 1.

(history contains input/output) There is a $\mathrm{poly}(\log T)$-time one-
query oracle algorithm $\mathsf{Input}$ and an $O(n)$-time oracle algorithm
$\mathsf{Output}$, both having input parameters $T,n$ and taking a string
$\tilde{h}\in\\{0,1\\}^{5T}$ as oracle, such that the following hold:

    1. (a)

When given $h$ as the oracle, $\mathsf{Input}_{T,n}$ takes an additional input
$i\in\\{0,1,\dotsc,5T-1\\}$ and outputs $f_{i}$.

    2. (b)

When given $h$ as the oracle, $\mathsf{Output}_{T,n}$ outputs
$z=\mathsf{Korten}(C,f)$.

  2. 2.

($\Pi_{1}$ verification of the history) There is an oracle algorithm $V$ with
input parameters $T,n$ such that the following holds:

    1. (a)

$V$ takes $\tilde{f}\in\\{0,1\\}^{T},\tilde{h}\in\\{0,1\\}^{5T}$ as oracles
and $C$ and $w\in\\{0,1\\}^{5\cdot(\log T+n)}$ as inputs. It runs in
$\mathrm{poly}(n)$ time.

    2. (b)

$h=\mathsf{History}(C,f)$ is the unique string from $\\{0,1\\}^{5T}$
satisfying the following:

$V^{f,h}(C,w)=1\qquad\text{for every $w\in\\{0,1\\}^{5\cdot(\log T+n)}$.}$

###### Proof.

From the definition of $\mathsf{History}(C,f)$, the construction of
$\mathsf{Input}_{T,n}$ and $\mathsf{Output}_{T,n}$ are straightforward. Now we
describe the verifier $V^{f,\tilde{h}}$, where $f\in\\{0,1\\}^{T}$ and
$\tilde{h}\in\\{0,1\\}^{5T}$. Note that here we fix the first oracle of $V$ to
be the input truth table $f$, while the second oracle $\tilde{h}$ can be any
string from $\\{0,1\\}^{5T}$.

First, $V$ reads $(i_{\star},j_{\star})$ from $\tilde{h}$. Note that the rest
of $\tilde{h}$ can be parsed as an array $\\{v_{i,j}\\}_{i,j}$ where
$i\in\\{0,1\dotsc,k\\}$ and $j\in\\{0,1,\dotsc,2^{i}\\}$. We will think of $V$
as performing at most $2^{|w|}$ checks, each of which _passes_ or _fails_. To
show the second item of the lemma, we need to show that (1) if a string
$\tilde{h}$ passes all the checks, then it must be the case that
$\tilde{h}=h$; and (2) $h$ passes all the checks.

Specifically, $V$ checks $\tilde{h}$ as follows:

  * •

The values written on the leaves of $\\{v_{i,j}\\}$ are indeed $f$. That is,
for every $j\in\\{0,1,\dotsc,2^{k}-1\\}$, check that $v_{k,j}$ is consistent
with the corresponding block in $f$.

  * •

For every $(i,j)>(i_{\star},j_{\star})$ such that $i<k$,
$C(v_{i,j})=v_{i+1,2j}\circ v_{i+1,2j+1}$. (That is, the value $v_{i,j}$ is
consistent with its two children.)

  * •

For every $(i,j)>(i_{\star},j_{\star})$ such that $i<k$, for every
$x\in\\{0,1\\}^{n}$ that is lexicographically smaller than $v_{i,j}$,
$C(x)\neq v_{i+1,2j}\circ v_{i+1,2j+1}$. (That is, the value $v_{i,j}$ is the
lexicographically first preimage of its two children.)

  * •

For every $x\in\\{0,1\\}^{n}$, $C(x)\neq v_{i_{\star}+1,2j_{\star}}\circ
v_{i_{\star}+1,2j_{\star}+1}$. (That is, the two children of
$(i_{\star},j_{\star})$ form a non-output of $C$; by the previous checks,
$(i_{\star},j_{\star})$ is the lexicographically largest such pair.)

  * •

For every $(i,j)\leq(i_{\star},j_{\star})$, $v_{i,j}=\bot$.

Note that the above can be implemented with a universal ($\forall$)
quantification over at most $5\cdot(\log T+n)$ bits. First, one can see that
by the definition of the correct history $h$ (3.6), $h$ passes all the checks
above. Second, one can indeed see that all the conditions above _uniquely
determine_ $h$, and therefore any $\tilde{h}$ passing all the checks must
equal $h$.∎

Again, it is easy to observe that 3.6 and 3.7 relativize.

######  Remark 3.8.

3.6 and 3.7 _relativize_ , in the sense that if $C$ is an oracle circuit
$C^{O}$ for some arbitrary oracle, 3.6 needs no modification since Algorithm
3.1 relativizes, and 3.7 holds with the only modification that $V$ now also
need to take $O$ as an oracle (since it needs to evaluate $C$).

##  4 Circuit Lower Bounds for $\Sigma_{2}\E$

In this section, we prove our near-maximum circuit lower bounds for
$\Sigma_{2}\E$ by providing a new single-valued $\mathsf{F}\Sigma_{2}\P$
algorithm for $\Avoid$.

Let $\\{C_{n}\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}\\}_{n\in\mathbb{N}}$ be a
$\P$-uniform family of circuits. We show that there is a single-valued
$\mathsf{F}\Sigma_{2}\P$ algorithm $A$ that, on input $1^{n}$, outputs a
canonical string that is outside the range of $C_{n}$ for infinitely many
$n\in\mathbb{N}$.

######  Theorem 4.1.

Let $\\{C_{n}\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}\\}_{n\in\mathbb{N}}$ be a
$\P$-uniform family of circuits. There is a single-valued
$\mathsf{F}\Sigma_{2}\P$ algorithm $A$ with one bit of advice such that for
infinitely many $n\in\mathbb{N}$, $A(1^{n})$ outputs
$y_{n}\in\\{0,1\\}^{2n}\setminus\mathrm{Range}(C_{n})$.

###### Proof.

We begin with some notation.

##### Notation.

Let $n^{(1)}$ be a large enough power of $2$,
$n^{(\ell)}=2^{2^{n^{(\ell-1)}}}$ for each integer $\ell>1$. Let
$n_{0}^{(\ell)}=n^{(\ell)}$ and $t^{(\ell)}=O\left(\log n_{0}^{(\ell)}\right)$
be parameters that we set later. For each $1\leq i\leq t^{(\ell)}$, let
$n^{(\ell)}_{i}:=\left(n^{(\ell)}_{i-1}\right)^{10}$. To show our algorithm
$A$ works on infinitely many input lengths, we will show that for every
$\ell\in\mathbb{N}$, there is an input length $n^{(\ell)}_{i}$ for some
$i\in\\{0,1,\dotsc,t^{(\ell)}\\}$ such that $A$ works.

Fix $\ell\in\mathbb{N}$. From now on, for convenience, we will use $n_{i}$ and
$t$ to denote $n^{(\ell)}_{i}$ and $t^{(\ell)}$, respectively.

##### Specifying $T_{i}$ and $f_{i}$.

For each input length $n_{i}$, we will specify a parameter
$T_{i}\in\mathbb{N}$ and a string $f_{i}\in\\{0,1\\}^{T_{i}}$. Our win-win
analysis is based on whether
$f_{i}\in\mathrm{Range}(\mathsf{GGM}_{T_{i}}[C_{n_{i}}])$ for each
$i\in\\{0,1,\dotsc,t\\}$.

Let $T_{0}:=2^{2n_{0}}\cdot 2n_{0}$ and $f_{0}$ be the concatenation of all
length-$2n_{0}$ strings (which has length $T_{0}$). From 3.4, we have that
$f_{0}\not\in\mathrm{Range}(\mathsf{GGM}_{T_{0}}[C_{n_{0}}])$. For every
$i\in[t]$, we define

$f_{i}:=\mathsf{History}(C_{n_{i-1}},f_{i-1}).$

From 3.6, this also means that we have set $T_{i}=5\cdot T_{i-1}$ for every
$i\in[t]$.

Let $t$ be the first integer such that $T_{t+1}\leq 4n_{t+1}$. Note that we
have $T_{i}=5^{i}\cdot T_{0}\leq 2^{3n_{0}+i\cdot\log 5}$ and
$n_{i}=(n_{0})^{10^{i}}=2^{\log n_{0}\cdot 10^{i}}$. Hence, we have that
$t\leq O(\log n_{0})$. (Also note that $n_{t}^{(\ell)}<n_{0}^{(\ell+1)}$.)

##### Description of our $\mathsf{F}\Sigma_{2}\P$ algorithm $A$.

Now, let $k\in\\{0,1,\dotsc,t\\}$ be the largest integer such that
$f_{k}\not\in\mathrm{Range}(\mathsf{GGM}_{T_{k}}[C_{n_{k}}])$. Since
$f_{0}\not\in\mathrm{Range}(\mathsf{GGM}_{T_{0}}[C_{n_{0}}])$, such a $k$ must
exist. Let $z:=\mathsf{Korten}(C_{n_{k}},f_{k})$. It follows from 3.3 that $z$
is not in the range of $C_{n_{k}}$. Our single-valued $\mathsf{F}\Sigma_{2}\P$
algorithm $A$ computes $z$ on input $1^{n_{k}}$ (see 2.2). That is, for some
$\ell_{1},\ell_{2}\leq\mathrm{poly}(n_{k})$:

  * •

There exists $\pi_{1}\in\\{0,1\\}^{\ell_{1}}$ such that for every
$\pi_{2}\in\\{0,1\\}^{\ell_{2}}$, $V_{A}(1^{n_{k}},\pi_{1},\pi_{2})$ prints
$z$, and

  * •

For every $\pi_{1}\in\\{0,1\\}^{\ell_{1}}$, there exists some
$\pi_{2}\in\\{0,1\\}^{\ell_{2}}$ such that $V_{A}(1^{n_{k}},\pi_{1},\pi_{2})$
prints either $z$ or $\bot$.

In more details, if $k<t$, then $V_{A}$ treats $\pi_{1}$ as an input to the
circuit $\mathsf{GGM}_{T_{k+1}}[C_{n_{k+1}}]$, and let

$\hat{f}_{k+1}:=\mathsf{GGM}_{T_{k+1}}[C_{n_{k+1}}](\pi_{1}).$

Here, the length of $\pi_{1}$ is $\ell_{1}:=n_{k+1}\leq\mathrm{poly}(n_{k})$.
If $k=t$, then $V_{A}$ defines $\hat{f}_{k+1}:=\pi_{1}$ and
$\ell_{1}:=T_{t+1}\leq\mathrm{poly}(n_{k})$. It is intended that
$\hat{f}_{k+1}=f_{k+1}=\mathsf{History}(C_{n_{k}},f_{k})$ (which $V_{A}$ needs
to verify). Note that in the case where $k<t$, since
$f_{k+1}\in\mathrm{Range}(\mathsf{GGM}_{T_{k+1}}[C_{n_{k+1}}])$, there indeed
exists some $\pi_{1}$ such that $\hat{f}_{k+1}=f_{k+1}$.

We note that 3.2 provides us “random access” to the (potentially very long)
string $\hat{f}_{k+1}$: given $\pi_{1}$ and $j\in[T_{k+1}]$, one can compute
the $j$-th bit of $\hat{f}_{k+1}$ in $\mathrm{poly}(n_{k})$ time. Also recall
from 3.7 that for each $i$, $f_{i+1}=\mathsf{History}(C_{n_{i}},f_{i})$
contains the string $f_{i}$, which can be retrieved by the oracle algorithm
$\mathsf{Input}$ described in Item 1 of 3.7. Therefore, for each $i$ from $k$
downto $1$, we can recursively define $\hat{f}_{i}$ such that
$(\hat{f}_{i})_{j}=\mathsf{Input}_{T_{i},n_{i}}^{\hat{f}_{i+1}}(j)$. We define
$\hat{f}_{0}$ to be the concatenation of all length-$(2n_{0})$ strings in the
lexicographical order, so $\hat{f}_{0}=f_{0}$. Applying the algorithm
$\mathsf{Input}$ recursively, we obtain an algorithm that given
$i\in\\{0,1,\dotsc,k\\}$ and $j\in\\{0,1,\dotsc,T_{i}-1\\}$, outputs the
$j$-th bit of $\hat{f}_{i}$. Since $\mathsf{Input}$ only makes one oracle
query, this algorithm runs in $\mathrm{poly}(n_{k})$ time.232323Note that the
definition of $f_{0}$ is so simple that one can directly compute the $j$-th
bit of $f_{0}$ in $\mathrm{poly}(n_{0})$ time.

Then, $V_{A}$ parses the second proof $\pi_{2}$ into $\pi_{2}=(i,w)$ where
$i\in\\{0,1,\dotsc,k\\}$ and $w\in\\{0,1\\}^{5(\log T_{i}+n_{i})}$. Clearly,
the length of $\pi_{2}$ is at most $\ell_{2}:=\log(k+1)+5(\log
T_{k}+n_{k})\leq\mathrm{poly}(n_{k})$. Now, let $V_{\mathsf{History}}$ be the
oracle algorithm in Item 2 of 3.7, we let $V_{A}(1^{n_{k}},\pi_{1},\pi_{2})$
check whether the following holds:

$V_{\mathsf{History}}^{\hat{f}_{i},\hat{f}_{i+1}}(C_{n_{i}},w)=1.$ (1)

If this is true, then $V_{A}$ outputs the string
$z:=\mathsf{Output}^{\hat{f}_{k+1}}_{T_{k},n_{k}}$, where $\mathsf{Output}$ is
the output oracle algorithm defined in Item 1 of 3.7. Otherwise, $V_{A}$
outputs $\bot$.

##### The correctness of $A$.

Before establishing the correctness of $A$, we need the following claim:

######  Claim 4.2.

$f_{k+1}=\hat{f}_{k+1}$ if and only if the following holds:

  * •

$V_{\mathsf{History}}^{\hat{f}_{i},\hat{f}_{i+1}}(C_{n_{i}},w)=1$ for every
$i\in\\{0,1,\dotsc,k\\}$ and for every $w\in\\{0,1\\}^{5(\log T_{i}+n_{i})}$.

###### Proof.

First, assume that $f_{k+1}=\hat{f}_{k+1}$. By Item 1a of 3.7, we have that
$\hat{f}_{i}=f_{i}$ for every $i\in\\{0,1,\dotsc,k+1\\}$. Recall that by
definition, $f_{i+1}=\mathsf{History}(C_{n_{i}},f_{i})$ for every
$i\in\\{0,1,\dotsc,k\\}$. Hence, by Item 2b of 3.7, we have that for every
$i\in\\{0,1,\dotsc,k\\}$, and for every $w\in\\{0,1\\}^{5(\log T_{i}+n_{i})}$,
$V_{\mathsf{History}}^{\hat{f}_{i},\hat{f}_{i+1}}(C_{n_{i}},w)=1$ holds.

For the other direction, suppose that for every $i\in\\{0,1,\dotsc,k\\}$ and
$w\in\\{0,1\\}^{5(\log T_{i}+n_{i})}$, we have that
$V_{\mathsf{History}}^{\hat{f}_{i},\hat{f}_{i+1}}(C_{n_{i}},w)=1$ holds. First
recall that $f_{0}=\hat{f}_{0}$ by definition. By an induction on $i\in[k+1]$
and (the uniqueness part of) Item 2b of 3.7, it follows that
$f_{i}=\hat{f}_{i}$ for every $i\in\\{0,1,\dotsc,k+1\\}$. In particular,
$f_{k+1}=\hat{f}_{k+1}$. ∎

Now we are ready to establish that $A$ is a single-valued
$\mathsf{F}\Sigma_{2}\P$ algorithm computing $z$ on input $1^{n_{k}}$. We
first prove the completeness of $A$; i.e., there is a proof $\pi_{1}$ such
that for every $\pi_{2}$, $V_{A}(1^{n_{k}},\pi_{1},\pi_{2})$ outputs
$z=\mathsf{Korten}(C_{n_{k}},f_{k})$. We set $\pi_{1}$ to be the following
proof: If $k<t$, then
$f_{k+1}\in\mathrm{Range}(\mathsf{GGM}_{T_{k+1}}[C_{n_{k+1}}])$, and we can
set $\pi_{1}\in\\{0,1\\}^{n_{k+1}}$ to be the input such that
$f_{k+1}=\mathsf{GGM}_{T_{k+1}}[C_{n_{k+1}}](\pi_{1})$; if $k=t$, then we
simply set $\pi_{1}=f_{k+1}$. Then, we have $f_{k+1}=\hat{f}_{k+1}$, and by
4.2, we know that $V_{A}$ will output $z=\mathsf{Korten}(C_{n_{k}},f_{k})$ on
every proof $\pi_{2}$.

Next, we show that for every $\pi_{1}$, there is some $\pi_{2}$ that makes
$V_{A}$ output either $z$ or $\bot$. It suffices to consider $\pi_{1}$ such
that for every $\pi_{2}$, $V_{A}(1^{n_{k}},\pi_{1},\pi_{2})\neq\bot$. In this
case, every invocation of Equation 1 holds, and thus by 4.2 we know that
$f_{k+1}=\hat{f}_{k+1}$. It follows that $\mathsf{Korten}(C_{n_{k}},f_{k})=z$
and $V_{A}$ will output $z$ regardless of $\pi_{2}$.

Finally, we generalize $A$ and $V_{A}$ to work on all inputs $1^{n}$. On input
$1^{n}$, $V_{A}$ calculates the largest $\ell$ such that $n^{(\ell)}\leq n$,
and also calculates the largest ${k^{\prime}}$ such that
$n_{k^{\prime}}^{(\ell)}\leq n$. If $n_{k^{\prime}}^{(\ell)}\neq n$, then
$V_{A}$ immediately outputs $\bot$ and halts. Otherwise, $V_{A}$ receives an
advice bit indicating whether $k^{\prime}=k^{(\ell)}$ where $k^{(\ell)}$ is
the largest integer such that
$f_{k^{(\ell)}}^{(\ell)}\not\in\mathrm{Range}(\mathsf{GGM}_{T_{k}^{(\ell)}}[C_{n_{k}^{(\ell)}}])$.
If this is the case, then $V_{A}$ runs the verification procedure above;
otherwise, it immediately outputs $\bot$ and halts. It is easy to see that
$V_{A}$ runs in $\mathrm{poly}(n)$ time, and is an infinitely-often single-
valued $\mathsf{F}\Sigma_{2}\P$ algorithm solving the range avoidance problem
of $\\{C_{n}\\}_{n\in\mathbb{N}}$. ∎

From 3.5 and 3.8, one can obverse that the proof above also relativizes. Hence
we have the following as well.

######  Theorem 4.3 (Relativized version of Theorem 4.1).

Let $\mathcal{O}\colon\\{0,1\\}^{*}\to\\{0,1\\}$ be any oracle. Let
$\\{C_{n}^{\mathcal{O}}\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}\\}_{n\in\mathbb{N}}$
be a $\P$-uniform family of $\mathcal{O}$-oracle circuits. There is a single-
valued $\mathsf{F}\Sigma_{2}\P^{\mathcal{O}}$ algorithm $A^{\mathcal{O}}$ with
one bit of advice such that for infinitely many $n\in\mathbb{N}$,
$A^{\mathcal{O}}(1^{n})$ outputs
$y_{n}\in\\{0,1\\}^{2n}\setminus\mathrm{Range}(C_{n}^{\mathcal{O}})$.

We omit the proof of the following corollary since it is superseded by the
results in the next section.

######  Corollary 4.4.

$\Sigma_{2}\E\not\subseteq\SIZE[2^{n}/n]$ and
$(\Sigma_{2}\E\cap\Pi_{2}\E)/_{1}\not\subseteq\SIZE[2^{n}/n]$. Moreover, these
results relativize: for every oracle $\mathcal{O}$,
$\Sigma_{2}\E^{\mathcal{O}}\not\subseteq\SIZE^{\mathcal{O}}[2^{n}/n]$ and
$(\Sigma_{2}\E^{\mathcal{O}}\cap\Pi_{2}\E^{\mathcal{O}})/_{1}\not\subseteq\SIZE^{\mathcal{O}}[2^{n}/n]$.

##  5 Circuit Lower Bounds for $\S_{2}\E$

In this section, we prove our near-maximum circuit lower bounds for
$\S_{2}\E/_{1}$ by giving a new single-valued $\mathsf{F}\S_{2}\P$ algorithm
for $\Avoid$.

###  5.1 Reed–Muller Codes

To prove maximum circuit lower bounds for $\S_{2}\E/_{1}$, we will need
several standard tools for manipulating Reed–Muller (RM) codes (i.e., low-
degree multi-variate polynomials).

For a polynomial $P\colon\mathbb{F}_{p}^{m}\to\mathbb{F}_{p}$, where
$\mathbb{F}_{p}$ is the finite field of $p$ elements, we use $\deg_{\rm
max}(P)$ to denote the maximum individual degree of variables in $P$. Let $p$
be a prime, $\Delta,m\in\mathbb{N}$. For a string
$S\in\\{0,1\\}^{\Delta^{m}}$, we use
$\mathsf{RM}_{\mathbb{F}_{p},\Delta,m}(S)$ to denote its Reed–Muller encoding
by extension: letting $H=\\{0,1,\dotsc,\Delta-1\\}$ and
$w_{1},\dotsc,w_{\Delta^{m}}\in H^{m}$ be the enumeration of all elements in
$H^{m}$ in the lexicographical order,
$\mathsf{RM}_{\mathbb{F}_{p},\Delta,m}(S)$ is the unique polynomial
$P\colon\mathbb{F}_{p}^{m}\to\mathbb{F}_{p}$ such that (1) $P(w_{i})=S_{i}$
for every $i\in[\Delta^{m}]$ and (2) $\deg_{\rm max}(P)\leq\Delta-1$.252525To
see the uniqueness of $P$, note that for every
$P\colon\mathbb{F}_{p}^{m}\to\mathbb{F}_{p}$ with $\deg_{\rm
max}(P)\leq\Delta-1$, the restriction of $P$ to $H^{m}$ uniquely determines
the polynomial $P$. Also, such $P$ can be constructed by standard
interpolation.

We also fix a Boolean encoding of $\mathbb{F}_{p}$ denoted as
$\mathsf{Enc}_{\mathbb{F}_{p}}\colon\mathbb{F}_{p}\to\\{0,1\\}^{\lceil\log
p\rceil}$. For simplicity, we can just map $z\in\\{0,1,\dotsc,p-1\\}$ to its
binary encoding. In particular,
$\mathsf{Enc}_{\mathbb{F}_{p}}(0)=0^{\lceil\log p\rceil}$ and
$\mathsf{Enc}_{\mathbb{F}_{p}}(1)=0^{\lceil\log p\rceil-1}\circ 1$.262626This
fact is useful because if we know a string $m\in\\{0,1\\}^{\lceil\log
p\rceil}$ encodes either $0$ or $1$, then we can decode it by only querying
the last bit of $m$. Now we further define
$\mathsf{BRM}_{\mathbb{F}_{p},\Delta,m}(S)$ by concatenating
$\mathsf{RM}_{\mathbb{F}_{p},\Delta,m}(S)$ with
$\mathsf{Enc}_{\mathbb{F}_{p}}$, thus obtaining a Boolean encoding again.
Formally, letting $P=\mathsf{RM}_{\mathbb{F}_{p},\Delta,m}(S)$ and
$w_{1},\dotsc,w_{p^{m}}\in\mathbb{F}_{p}^{m}$ be the enumeration of all
elements from $\mathbb{F}_{p}^{m}$ in the lexicographic order, we define
$\mathsf{BRM}_{\mathbb{F}_{p},\Delta,m}(S)=\mathsf{Enc}_{\mathbb{F}_{p}}(P(w_{1}))\circ\mathsf{Enc}_{\mathbb{F}_{p}}(P(w_{2}))\circ\dotsc\circ\mathsf{Enc}_{\mathbb{F}_{p}}(P(w_{p^{m}}))$.
We remark that for every $i\in\left[\Delta^{m}\right]$, in
$\mathrm{poly}(m,\log p)$ time one can compute an index
$i^{\prime}\in[p^{m}\cdot\lceil\log p\rceil]$ such that
$\mathsf{BRM}_{\mathbb{F}_{p},\Delta,m}(S)_{i^{\prime}}=S_{i}$.

We need three properties of Reed–Muller codes, which we explain below.

##### Self-correction for polynomials.

We first need the following self-corrector for polynomials, which efficiently
computes the value of $P$ on any input given an oracle that is close to a low-
degree polynomial $P$. (In other words, it is a _local decoder_ for the
Reed–Muller code.)

######  Lemma 5.1 (A self-corrector for polynomials, cf. [GS92, Sud95]).

There is a probabilistic oracle algorithm $\mathsf{PCorr}$ such that the
following holds. Let $p$ be a prime, $m,\Delta\in\mathbb{N}$ such that
$\Delta<p/3$. Let $g\colon\mathbb{F}_{p}^{m}\to\mathbb{F}_{p}$ be a function
such that for some polynomial $P$ of total degree at most $\Delta$,

$\Pr_{\vec{x}\leftarrow{\mathbb{F}_{p}^{m}}}[g(\vec{x})\neq P(\vec{x})]\leq
1/4.$

Then for all $\vec{x}\in\mathbb{F}_{p}^{m}$,
$\mathsf{PCorr}^{g}(p,m,\Delta,\vec{x})$ runs in time
$\mathrm{poly}(\Delta,\log p,m)$ and outputs $P(\vec{x})$ with probability at
least $2/3$.

##### Low-max-degree test.

We also need the following efficient tester, which checks whether a given
polynomial has maximum individual degree at most $\Delta$ or is far from such
polynomials.272727To obtain the theorem below, we set the parameter $\delta$
and $\varepsilon$ from [BFL91, Remark 5.15] to be
$\min\left(\frac{1}{200n^{2}(\Delta+1)},1/2p\right)$ and
$\min\left(\frac{1}{400n^{3}(\Delta+1)},1/2p\right)$, respectively.

######  Lemma 5.2 (Low-max-degree tester [BFL91, Remark 5.15]).

Let $n,\Delta,p\in\mathbb{N}$ be such that $p\geq 20\cdot(\Delta+1)^{2}\cdot
n^{2}$ and $p$ is a prime. There is a probabilistic non-adaptive oracle
machine $\mathsf{LDT}$ such that the following holds. Let
$g\colon\mathbb{F}_{p}^{n}\to\mathbb{F}_{p}$. Then for
$\delta=3n^{2}\cdot(\Delta+1)/p$, it holds that

  1. 1.

if $\deg_{\rm max}(g)\leq\Delta$, then $\mathsf{LDT}^{g}(p,n,\Delta)$ accepts
with probability $1$,

  2. 2.

if $g$ is at least $\delta$-far from every polynomial with maximum individual
degree at most $\Delta$, then $\mathsf{LDT}^{g}(p,n,\Delta)$ rejects with
probability at least $2/3$, and

  3. 3.

$\mathsf{LDT}$ runs in $\mathrm{poly}(p)$ time.

##### Comparing two RM codewords.

Lastly, we show an efficient algorithm that, given oracle access to two
codewords of $\mathsf{RM}_{\mathbb{F}_{p},\Delta,m}$, computes the
lexicographically first differing point between the respective messages of the
two codewords.

######  Lemma 5.3 (Comparing two RM codewords).

Let $p$ be a prime. Let $m,\Delta\in\mathbb{N}$ be such that
$m\cdot\Delta<p/2$. There is a probabilistic oracle algorithm $\mathsf{Comp}$
that takes two polynomials $f,g\colon\mathbb{F}_{p}^{m}\to\mathbb{F}_{p}$ as
oracles, such that if both $\deg_{\rm max}(f)$ and $\deg_{\rm max}(g)$ are at
most $\Delta$, then the following holds with probability at least $9/10$:

  * •

If $f\neq g$, then $\mathsf{Comp}^{f,g}(p,m,\Delta)$ outputs the
lexicographically smallest element $w$ in $H^{m}$ such that $f(w)\neq g(w)$,
where $H=\\{0,1,\dotsc,\Delta-1\\}$.282828Since both $f$ and $g$ have max
degree at most $\Delta$, their values are completely determined by their
restrictions on $H^{m}$. Hence, if $f\neq g$, then such $w$ must exist.

  * •

If $f=g$, then $\mathsf{Comp}^{f,g}(p,m,\Delta)$ outputs $\bot$.

  * •

$\mathsf{Comp}$ makes at most $\mathrm{poly}(m\cdot\Delta)$ queries to both
$f$ and $g$, and runs in $\mathrm{poly}(m\cdot\Delta\cdot\log p)$ time.

###### Proof.

Our proof is similar to the proof from [Hir15], which only considers multi-
linear polynomials. Our algorithm $\mathsf{Comp}^{f,g}(p,m,\Delta)$ works as
follows:

  1. 1.

The algorithm has $m$ stages, where the $i$-th stage aims to find the $i$-th
entry of $w$. At the end of the $i$-th stage, the algorithm obtains a
length-$i$ prefix of $w$.

  2. 2.

For every $i\in[m]$:

    1. (a)

Let $w_{<i}\in H^{i-1}$ be the current prefix. For every
$h\in\\{0,1,\dotsc,\Delta-1\\}$, we run a randomized polynomial identity test
to check whether the restricted polynomial $f(w_{<i},h,\cdot)$ and
$g(w_{<i},h,\cdot)$ are the same, with error at most
$\frac{1}{10m|H|}$.292929Note that these two polynomials have total degree at
most $m\cdot\Delta<p/2$. Hence if they are different, their values on a random
element from $\mathbb{F}_{p}^{m-i}$ are different with probability at least
$1/2$. Hence the desired error level can be achieved by sampling $O(\log
m+\log\Delta)$ random points from $\mathbb{F}^{m-i}$ and checking whether
$f(w_{<i},h,\cdot)$ and $g(w_{<i},h,\cdot)$ have the same values.

    2. (b)

We set $w_{i}$ to be the smallest $h$ such that our test above reports that
$f(w_{<i},h,\cdot)$ and $g(w_{<i},h,\cdot)$ are distinct. If there is no such
$h$, we immediately return $\bot$.

By a union bound, all $mH$ polynomial identity testings are correct with
probability at least $9/10$. In this case, if $f=g$, then the algorithm
outputs $\bot$ in the first stage. If $f\neq g$, by induction on $i$, we can
show that for every $i\in[m]$, $w_{\leq i}$ is the lexicographically smallest
element from $H^{m}$ such that $f(w_{\leq i},\cdot)$ and $g(w_{\leq i},\cdot)$
are distinct, which implies that the output $w$ is also the lexicographically
smallest element $w$ in $H^{m}$ such that $f(w)\neq g(w)$. ∎

###  5.2 Encoded History and $\S_{2}\BPP$ Verification

Next, we define the following encoded history.

######  Definition 5.4.

Let $C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}$ be a circuit, and
$f\in\\{0,1\\}^{T}$ be a “hard truth table” in the sense that
$f\not\in\mathrm{Range}(\mathsf{GGM}_{T}[C])$. Let $k$,
$(i_{\star},j_{\star})$, and $\\{v_{i,j}\\}_{i,j}$ be defined as in Algorithm
3.1. Let $S$ be the concatenation of ${\sf enc}(v_{i,j})$ for every
$i\in\\{0,1,\dotsc,k-1\\}$, $j\in\\{0,1,\dotsc,2^{i}-1\\}$, in the reserve
lexicographical order of $(i,j)$, padded with zeros at the end to length
exactly $5T$. (Recall that ${\sf enc}(v_{i,j})$ was defined in 3.6.) Let $p$
be the smallest prime that is at least $20\cdot\log^{5}T$, and $m$ be the
smallest integer such that $(\log T)^{m}\geq 5\cdot T$.

The _encoded computational history_ of $\mathsf{Korten}(C,f)$, denoted as

$\widetilde{\mathsf{History}}(C,f),$

consists of $(i_{\star},j_{\star})$, concatenated with
$\mathsf{BRM}_{\mathbb{F}_{p},\log T,m}(S)$.

The length of the encoded history is at most

$\left\lceil\log(40\cdot\log^{5}T)\right\rceil\cdot(40\cdot\log^{5}T)^{\log(5T)/\log\log
T+1}+2\log T\leq T^{6}$

for all sufficiently large $T$, and for convenience we always pad zeros at the
end so that its length becomes exactly $T^{6}$.303030For simplicity even for
$T$ such that the length of the encoded history is longer than $T^{6}$, we
will pretend its length is exactly $T^{6}$ throughout this section. This does
not affect the analysis in our main theorem Theorem 5.7 since there we only
care about sufficiently large $T$.

Recall that the original computational history $\mathsf{History}(C,f)$ is
simply the concatenation of $(i_{\star},j_{\star})$ and $S$. In the encoded
version, we encode its $S$ part by the Reed–Muller code instead. In the rest
of this section, when we say history, we always mean the encoded history
$\widetilde{\mathsf{History}}(C,f)$ instead of the vanilla history
$\mathsf{History}(C,f)$.

We need the following lemma.

######  Lemma 5.5.

Let $n,T\in\mathbb{N}$ be such that $\log T\leq n\leq T$. Let
$C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}$ be a circuit and
$f\in\\{0,1\\}^{T}\setminus\mathrm{Range}(\mathsf{GGM}_{T}[C])$. Let
$h\coloneqq\widetilde{\mathsf{History}}(C,f)$ and
$z\coloneqq\mathsf{Korten}(C,f)$.

  1. 1.

(history contains input/output) There is a $\mathrm{poly}(\log T)$-time oracle
algorithm $\mathsf{Input}$ and an $O(n)$-time oracle algorithm
$\mathsf{Output}$, both of which have input parameters $T,n$ and take a string
$\tilde{h}\in\\{0,1\\}^{T^{6}}$ as oracle, such that the following hold:

    1. (a)

$\mathsf{Input}_{T,n}$ makes a single query to its oracle; when given $h$ as
the oracle, $\mathsf{Input}_{T,n}$ takes an additional input
$i\in\\{0,1,\dotsc,T^{6}-1\\}$ and outputs $f_{i}$.

    2. (b)

$\mathsf{Output}_{T,n}$ makes at most $4n$ queries to its oracle; when given
$h$ as the oracle, $\mathsf{Output}_{T,n}$ outputs $z=\mathsf{Korten}(C,f)$.

  2. 2.

($\S_{2}\BPP$ verification of the history) There is a randomized oracle
algorithm $V$ with input parameters $T,n$ such that the following hold:

    1. (a)

$V$ takes strings
$\tilde{f}\in\\{0,1\\}^{T},\pi_{1},\pi_{2}\in\\{0,1\\}^{T^{6}}$ as oracles,
the circuit $C$, an integer $i\in\left[T^{6}\right]$, and
$\varepsilon\in(0,1)$ as input, and runs in
$\mathrm{poly}(n,\log\varepsilon^{-1})$ time.

    2. (b)

For every $\pi\in\\{0,1\\}^{T^{6}}$ and every $i\in\\{0,1,\dotsc,T^{6}-1\\}$,
we have that

$\Pr\left[V^{f,\pi,h}_{T,n}(C,i,\varepsilon)=h_{i}\right]\geq
1-\varepsilon\quad\text{and}\quad\Pr\left[V^{f,h,\pi}_{T,n}(C,i,\varepsilon)=h_{i}\right]\geq
1-\varepsilon.$

###### Proof.

Again, the algorithms $\mathsf{Input}_{T,n}$ and $\mathsf{Output}_{T,n}$ can
be constructed in a straightforward way.313131To see that
$\mathsf{Output}_{T,n}$ makes at most $4n$ queries: Note that
$\mathsf{Output}$ first reads the pair $(i_{\star},j_{\star})$ from $h$, and
then reads two corresponding blocks from $v_{i,j}$ encoded in $h$. In total,
it reads at most $2\log T+2n\leq 4n$ bits from $h$. So we focus on the
construction of $V$. Let $p,m,k\in\mathbb{N}$ be as in 5.4. We also set
$\mathbb{F}=\mathbb{F}_{p}$ and $\Delta=\log T$ in the rest of the proof.

Our $V$ always first _selects_ one of the oracles $\pi_{1}$ and $\pi_{2}$ (say
$\pi_{\mu}$ for $\mu\in\\{1,2\\}$), and then outputs $\pi_{\mu}(i)$. Hence, in
the following, we say that $V$ selects $\pi_{\mu}$ to mean that $V$ outputs
$\pi_{\mu}(i)$ and terminates. Given $\pi_{1}$ and $\pi_{2}$, let
$g_{1},g_{2}\colon\mathbb{F}^{m}\to\mathbb{F}$ be the (potential) RM codewords
encoded in $\pi_{1}$ and $\pi_{2}$, respectively.323232Technically $\pi_{1}$
and $\pi_{2}$ are supposed to contain the RM codewords concatenated with
$\mathsf{Enc}_{\mathbb{F}_{p}}\colon\mathbb{F}_{p}\to\\{0,1\\}^{\lceil\log
p\rceil}$. From now on, we will assume that $i$ points to an entry in the
encoded history $g_{1}$ or $g_{2}$ instead of the encoded pair of integers
$(i_{\star},j_{\star})$. We will discuss the other case at the end of the
proof.

##### Low-max-degree test and self-correction.

We first run $\mathsf{LDT}^{g_{1}}(p,m,\Delta-1)$ and
$\mathsf{LDT}^{g_{2}}(p,m,\Delta-1)$ for $c_{1}$ times, where $c_{1}$ is a
sufficiently large constant. Recall that $p\geq 20\cdot\log^{5}T$,
$m=\left\lceil\log\left(5T\right)/\log\log T\right\rceil$, and $\Delta=\log
T$. It follows that $p\geq 20\cdot((\Delta-1)+1)^{2}\cdot m^{2}$, which
satisfies the condition of 5.2. We also note that
$3m^{2}\cdot((\Delta-1)+1)/p<1/4$. Hence, by 5.2, if $g_{1}$ is $1/4$-far from
all polynomials with maximum individual degree at most $\Delta-1$, then
$\mathsf{LDT}^{g_{1}}(p,m,\Delta-1)$ rejects with probability $2/3$, and
similarly for $g_{2}$.

Now, if any of the runs on $\mathsf{LDT}^{g_{1}}(p,m,\Delta-1)$ rejects, $V$
selects $\pi_{2}$, and if any of the runs on
$\mathsf{LDT}^{g_{2}}(p,m,\Delta-1)$ rejects, $V$ selects $\pi_{1}$.333333As a
minor detail, if both $g_{1}$ and $g_{2}$ are rejected by some runs, $V$
selects $\pi_{2}$. In other words, $V$ first _disqualifies_ the oracles that
do not pass the low-max-degree test. We set $c_{1}$ to be large enough so that
conditioning on the event that $V$ does not terminate yet, with probability at
least $0.99$, both $g_{1}$ and $g_{2}$ are $1/4$-close to polynomials
$\widetilde{g}_{1}\colon\mathbb{F}_{p}^{m}\to\mathbb{F}$ and
$\widetilde{g}_{2}\colon\mathbb{F}_{p}^{m}\to\mathbb{F}$, respectively, where
$\deg_{\rm max}(\widetilde{g}_{1})$ and $\deg_{\rm max}(\widetilde{g}_{2})$
are at most $\Delta-1$.

We can then use $\mathsf{PCorr}^{g_{1}}(p,m,m\cdot(\Delta-1),\cdot)$ and
$\mathsf{PCorr}^{g_{2}}(p,m,m\cdot(\Delta-1),\cdot)$ to access the polynomials
$\widetilde{g}_{1}$ and $\widetilde{g}_{2}$. (Note that
$m\cdot(\Delta-1)<p/3$, which satisfies the condition of 5.1). We repeat them
each $O(\log T+\log m)$ times to make sure that on a single invocation, they
return the correct values of $\widetilde{g}_{1}$ and $\widetilde{g}_{2}$
respectively with probability at least $1-1/(mT)^{c_{2}}$ for a sufficiently
large constant $c_{2}$. By 5.1, each call to
$\mathsf{PCorr}^{g_{1}}(p,m,m\cdot(\Delta-1),\cdot)$ or
$\mathsf{PCorr}^{g_{2}}(p,m,m\cdot(\Delta-1),\cdot)$ takes
$\mathrm{polylog}(T)$ time.

##### Selecting the better polynomial.

From now on, we refine what it means when $V$ selects $\pi_{\mu}$: now it
means that $V$ outputs the bit corresponding to $i$ in $\widetilde{g}_{\mu}$
(recall that we are assuming that $i$ points to an entry in the encoded
history $g_{1}$ or $g_{2}$).

Let $\\{v^{1}_{i,j}\\}$ and $\\{v^{2}_{i,j}\\}$ be the encoded histories in
$\widetilde{g}_{1}$ and $\widetilde{g}_{2}$. Then $V$ uses
$\mathsf{Comp}^{\widetilde{g}_{1},\widetilde{g}_{2}}(p,m,\Delta-1)$ to find
the lexicographically largest $(i^{\prime},j^{\prime})$ such that
$v^{1}_{i^{\prime},j^{\prime}}\neq v^{2}_{i^{\prime},j^{\prime}}$.343434Recall
that the $\\{v_{i,j}\\}$ is encoded in the reverse lexicographic order (5.4).
Note that $\mathsf{Comp}^{\widetilde{g}_{1},\widetilde{g}_{2}}(p,m,\Delta-1)$
makes at most $\mathrm{poly}(m\cdot\Delta)$ queries to both
$\widetilde{g}_{1}$ and $\widetilde{g}_{2}$. By making $c_{2}$ large enough,
we know that $\mathsf{Comp}$ operates correctly with probability at least
$0.8$. By operating correctly, we mean that (1) if
$\widetilde{g}_{1}\neq\widetilde{g}_{2}$, $\mathsf{Comp}$ finds the correct
$(i^{\prime},j^{\prime})$ and (2) If $\widetilde{g}_{1}=\widetilde{g}_{2}$,
$\mathsf{Comp}$ returns $\bot$.353535From 5.3,
$\mathsf{Comp}^{\widetilde{g}_{1},\widetilde{g}_{2}}(p,m,\Delta-1)$ itself
operates correctly with probability at least $0.9$. But the access to
$\widetilde{g}_{1}$ (similarly to $\widetilde{g}_{2}$) is provided by
$\mathsf{PCorr}^{g_{1}}(p,m,m\cdot(\Delta-1),\cdot)$, which may err with
probability at most $1/(mT)^{c_{2}}$. So we also need to take a union bound
over all the bad events that a query from $\mathsf{Comp}$ to
$\widetilde{g}_{1}$ or $\widetilde{g}_{2}$ is incorrectly answered.

In what follows, we assume that $\mathsf{Comp}$ operates correctly. If
$\mathsf{Comp}$ returns $\bot$, then $V$ simply selects $\pi_{1}$. Otherwise,
there are several cases:

  1. 1.

$i^{\prime}=k$. In this case, $\widetilde{g}_{1}$ and $\widetilde{g}_{2}$
disagree on their leaf values, which intend to encode $f$. $V$ queries $f$ to
figure out which one has the correct value, and selects the corresponding
oracle. (Note that at most one of them can be consistent with $f$. If none of
them are consistent, then $V$ selects $\pi_{1}$.)

From now on, assume $i^{\prime}<k$ and set
$\alpha=v^{1}_{i^{\prime}+1,2j^{\prime}}\circ
v^{1}_{i^{\prime}+1,2j^{\prime}+1}$. Note that by the definition of
$(i^{\prime},j^{\prime})$, it holds that
$\alpha=v^{2}_{i^{\prime}+1,2j^{\prime}}\circ
v^{2}_{i^{\prime}+1,2j^{\prime}+1}$ as well.

  2. 2.

$i^{\prime}<k$ and both $v^{1}_{i^{\prime},j^{\prime}}$ and
$v^{2}_{i^{\prime},j^{\prime}}$ are not $\bot$. In this case, $V$ first checks
whether both of them are in $C^{-1}(\alpha)$ (it can be checked by testing
whether $C(v^{1}_{i^{\prime},j^{\prime}})=\alpha$ and
$C(v^{2}_{i^{\prime},j^{\prime}})=\alpha$). If only one of them is contained
in $C^{-1}(\alpha)$, $V$ selects the corresponding oracle. If none of them are
contained, $V$ selects $\pi_{1}$. Finally, if both are contained in
$C^{-1}(\alpha)$, $V$ checks which one is lexicographically smaller, and
selects the corresponding oracle.

  3. 3.

$i^{\prime}<k$, and one of the $v^{1}_{i^{\prime},j^{\prime}}$ and
$v^{2}_{i^{\prime},j^{\prime}}$ is $\bot$. Say that
$v^{b}_{i^{\prime},j^{\prime}}=\bot$ for some $b\in\\{1,2\\}$, and denote
$\bar{b}:=3-b$ as the index of the other proof. In this case, let
$(i_{\circ},j_{\circ})$ denote the predecessor of $(i^{\prime},j^{\prime})$ in
terms of the reverse lexicographical order (that is, the smallest pair that is
lexicographically greater than $(i^{\prime},j^{\prime})$). Since
$\mathsf{Comp}$ operates correctly, we have that
$v^{1}_{i_{\circ},j_{\circ}}=v^{2}_{i_{\circ},j_{\circ}}$. If
$v^{1}_{i_{\circ},j_{\circ}}=\bot$, then $\pi_{\bar{b}}$ has to be incorrect
(since by 3.6, $\bot$’s form a contiguous suffix of the history), and $V$
selects $\pi_{b}$. Otherwise, if $v^{\bar{b}}_{i^{\prime},j^{\prime}}\in
C^{-1}(\alpha)$, then $\pi_{b}$ is incorrect (as it claims that
$C^{-1}(\alpha)=\varnothing$), and $V$ selects $\pi_{\bar{b}}$. Otherwise, $V$
selects $\pi_{b}$.

##### Analysis.

Now we show that $\Pr\left[V_{T,n}^{f,h,\pi}(i)=h(i)\right]\geq 2/3$. (The
proof for $\Pr\left[V_{T,n}^{f,\pi,h}(i)=h(i)\right]\geq 2/3$ is symmetric.)
To get the desired $\varepsilon$ error probability, one can simply repeat the
above procedure $O(\log 1/\varepsilon)$ times and output the majority.

First, by 5.2, $\mathsf{LDT}^{g_{1}}(p,m,\Delta-1)$ passes with probability
$1$. If some of the runs of $\mathsf{LDT}^{g_{2}}(p,m,\Delta-1)$ rejects, then
$V$ selects $h$. Otherwise, we know that with probability at least $0.99$,
$\mathsf{PCorr}^{g_{1}}(p,m,m\cdot(\Delta-1),\cdot)$ and
$\mathsf{PCorr}^{g_{2}}(p,m,m\cdot(\Delta-1),\cdot)$ provide access to
polynomials $\widetilde{g}_{1}$ and $\widetilde{g}_{2}$ with maximum
individual degree at most $\Delta-1$, where $\widetilde{g}_{1}$ encodes the
correct history values $\\{v_{i,j}\\}_{i,j}$ of $\mathsf{Korten}(C,f)$.

Then, assuming $\mathsf{Comp}$ operates correctly (which happens with
probability at least $0.8$), if $\widetilde{g}_{1}=\widetilde{g}_{2}$, then
the selection of $V$ does not matter. Now we assume
$\widetilde{g}_{1}\neq\widetilde{g}_{2}$.

We will verify that in all three cases above, $h$ (as the first oracle) is
selected by $V$. In the first case, by definition, all leaf values in $h$ are
consistent with $f$, and hence $h$ is selected. In the second case, since $h$
contains the correct history values, we know that
$v^{1}_{i^{\prime},j^{\prime}}$ must be the smallest element from
$C^{-1}(\alpha)$, so again $h$ is selected. In the last case: (1) if
$v^{1}_{i_{\circ},j_{\circ}}=\bot$, then $v^{1}_{i^{\prime},j^{\prime}}$ has
to be $\bot$ as well, thus $h$ is selected; (2) if
$v^{1}_{i_{\circ},j_{\circ}}\neq\bot$ and
$v^{1}_{i^{\prime},j^{\prime}}=\bot$, then $C^{-1}(\alpha)=\varnothing$, and
since the other proof $\pi$ claims some element
$v^{2}_{i^{\prime},j^{\prime}}\in C^{-1}(\alpha)$, $h$ is selected; and (3) if
$v^{1}_{i_{\circ},j_{\circ}}\neq\bot$ and
$v^{1}_{i^{\prime},j^{\prime}}\neq\bot$, then $\pi$ claims that
$C^{-1}(\alpha)=\varnothing$ and we can check that
$v^{1}_{i^{\prime},j^{\prime}}\in C^{-1}(\alpha)$, therefore $h$ is selected
as well.

##### The remaining case: $i$ points to the location of
$(i_{\star},j_{\star})$.

In this case, $V$ still runs the algorithm described above to make a
selection. Indeed, if $\mathsf{Comp}$ does not return $\bot$, $V$ operates
exactly the same. But when $\mathsf{Comp}$ returns $\bot$, $V$ cannot simply
select $\pi_{1}$ since we need to make sure that $V$ selects the oracle
corresponding to $h$ (it can be either $\pi_{1}$ or $\pi_{2}$). Hence, in this
case, $V$ first reads $(i_{\star}^{1},j_{\star}^{1})$ and
$(i_{\star}^{2},j_{\star}^{2})$ from $\pi_{1}$ and $\pi_{2}$. If they are the
same, $V$ simply selects $\pi_{1}$. Otherwise, for $b\in[2]$, $V$ checks
whether $v^{b}_{i_{\star}^{b},j_{\star}^{b}}=\bot$, and select the one that
satisfies this condition. (If none of the
$v^{b}_{i_{\star}^{b},j_{\star}^{b}}$ are, then $V$ selects $\pi_{1}$). If
both of $v^{b}_{i_{\star}^{b},j_{\star}^{b}}$ are $\bot$, $V$ selects the
$\mu\in[2]$ such that $(i_{\star}^{\mu},j_{\star}^{\mu})$ is larger.

Now, we can verify that $V_{T,n}^{f,h,\pi}$ selects $h$ with high probability
as well. (To see this, note that in the correct history,
$(i_{\star},j_{\star})$ points to the lexicographically largest all-zero
block.)

Finally, the running time bound follows directly from the description of $V$.
∎

####  5.2.1 A remark on relativization

Perhaps surprisingly, although 5.5 heavily relies on arithmetization tools
such as Reed–Muller encoding and low-degree tests, it in fact also
relativizes. To see this, the crucial observation is that, similarly to 3.7,
the verifier $V$ from 5.5 only needs _black-box access_ to the input circuit
$C$, meaning that it only needs to evaluate $C$ on certain chosen input.
Hence, when $C$ is actually an oracle circuit $C^{\mathcal{O}}$ for some
arbitrary oracle $\mathcal{O}$, the only modification we need is that $V$ now
also takes $\mathcal{O}$ as an oracle.

######  Remark 5.6.

5.4 and 5.5 _relativize_ , in the sense that if $C$ is an oracle circuit
$C^{\mathcal{O}}$ for some arbitrary oracle, 5.4 needs no modification since
3.6 relativizes, and 5.5 holds with the only modification that $V$ now also
needs to take $\mathcal{O}$ as an oracle (since it needs to evaluate $C$).

Indeed, the remark above might sound strange at first glance: arguments that
involve PCPs often do not _relativize_ , and the encoded history
$\widetilde{\mathsf{History}}(C,f)$ looks similar to a PCP since it enables
$V$ to perform a probabilistic local verification. However, a closer
inspection reveals a key difference: the circuit $C$ is always treated as a
black box—both in the construction of history (3.6) and in the construction of
the encoded history (5.4). That is, the arithmetization in the encoded history
_does not arithmetize_ the circuit $C$ itself.

###  5.3 Lower Bounds for $\S_{2}\E$

Let $\\{C_{n}:\\{0,1\\}^{n}\to\\{0,1\\}^{2n}\\}$ be a $\P$-uniform family of
circuits. We show that there is a single-valued $\mathsf{F}\S_{2}\P$ algorithm
$\mathcal{A}$ such that for infinitely many $n\in\mathbb{N}$, on input
$1^{n}$, $\mathcal{A}(1^{n})$ outputs a canonical string that is outside the
range of $C_{n}$.

######  Theorem 5.7.

Let $\\{C_{n}\colon\\{0,1\\}^{n}\to\\{0,1\\}^{2n}\\}_{n\in\mathbb{N}}$ be a
$\P$-uniform family of circuits. There is a sequence of valid outputs
$\\{y_{n}\in\\{0,1\\}^{2n}\setminus\mathrm{Range}(C_{n})\\}_{n\in\mathbb{N}}$
and a single-valued $\mathsf{F}\S_{2}\P$ algorithm $A$ with one bit of advice,
such that for infinitely many $n\in\mathbb{N}$, $A(1^{n})$ outputs $y_{n}$.

###### Proof.

Our proof proceeds similarly to the proof of the previous Theorem 4.1. We will
follow the same notation.

##### Notation.

Let $n^{(1)}$ be a large enough power of $2$,
$n^{(\ell)}=2^{2^{n^{(\ell-1)}}}$ for each integer $\ell>1$. Let
$n_{0}^{(\ell)}=n^{(\ell)}$ and $t^{(\ell)}=O\left(\log n_{0}^{(\ell)}\right)$
be parameters that we set later. For each $1\leq i\leq t^{(\ell)}$, let
$n^{(\ell)}_{i}:=\left(n^{(\ell)}_{i-1}\right)^{10}$. To show our algorithm
$A$ works on infinitely many input lengths, we will show that for every
$\ell\in\mathbb{N}$, there is an input length $n^{(\ell)}_{i}$ for some
$i\in\left[t^{(\ell)}\right]$ such that $A$ works.

Fix $\ell\in\mathbb{N}$. From now on, for convenience, we will use $n_{i}$ and
$t$ to denote $n^{(\ell)}_{i}$ and $t^{(\ell)}$, respectively.

##### Specifying $T_{i}$ and $f_{i}$.

For each input length $n_{i}$, we will specify a parameter
$T_{i}\in\mathbb{N}$ and a string $f_{i}\in\\{0,1\\}^{T_{i}}$. Our win-win
analysis is based on whether
$f_{i}\in\mathrm{Range}(\mathsf{GGM}_{T_{i}}[C_{n_{i}}])$ for each
$i\in\\{0,1,\dotsc,t\\}$.

Let $T_{0}:=2^{2n_{0}}\cdot 2n_{0}$ and $f_{0}$ be the concatenation of all
length-$2n_{0}$ strings (which has length $T_{0}$). From 3.4, we have that
$f_{0}\not\in\mathrm{Range}(\mathsf{GGM}_{T_{0}}[C_{n_{0}}])$. For every
$i\in[t]$, we define

$f_{i}=\widetilde{\mathsf{History}}(C_{n_{i-1}},f_{i-1}).$

From 5.4, this also means that we have set $T_{i}=T_{i-1}^{6}$ for every
$i\in[t]$.

Let $t$ be the first integer such that $T_{t+1}\leq n_{t+1}$. Note that we
have $T_{i}=(T_{0})^{6^{i}}\leq 2^{3n_{0}\cdot 6^{i}}$ and
$n_{i}=(n_{0})^{10^{i}}=2^{\log n_{0}\cdot 10^{i}}$. Hence, we have that
$t\leq O(\log n_{0})$. (Also note that $n_{t}^{(\ell)}<n_{0}^{(\ell+1)}$.)

##### Description of our $\mathsf{F}\S_{2}\P$ algorithm $A$.

Now, let $k\in\\{0,1,\dotsc,t\\}$ be the largest integer such that
$f_{k}\not\in\mathrm{Range}(\mathsf{GGM}_{T_{k}}[C_{n_{k}}])$. Since
$f_{0}\not\in\mathrm{Range}(\mathsf{GGM}_{T_{0}}[C_{n_{0}}])$, such a $k$ must
exist. Let $z:=\mathsf{Korten}(C_{n_{k}},f_{k})$, it follows from 3.3 that $z$
is not in the range of $C_{n_{k}}$ (i.e.,
$z\in\\{0,1\\}^{2n_{k}}\setminus\mathrm{Range}(C_{n_{k}})$). Our single-valued
$\mathsf{F}\S_{2}\P$ algorithm $A$ computes $z$ on input $1^{n_{k}}$ (see
2.2).

We will first construct an $\S_{2}\BPP$ verifier $V$ that computes $z$ in
polynomial time on input $1^{n_{k}}$, and then use the fact that all
$\S_{2}\BPP$ verifiers can be turned into equivalent $\S_{2}\P$ verifiers with
a polynomial-time blow-up [Can96, RS98], from which we can obtain the desired
verifier $V_{A}$ for $A$.

##### Description of an $\S_{2}\BPP$ verifier $V$ computing $z$.

Formally, $V$ is a randomized polynomial-time algorithm that takes $1^{n_{k}}$
and two witnesses $\pi_{1},\pi_{2}\in\\{0,1\\}^{n_{k+1}}$ as input, and we aim
to establish the following:  There exists $\omega\in\\{0,1\\}^{n_{k+1}}$ such
that for every $\pi\in\\{0,1\\}^{n_{k+1}}$, we have
$\Pr[V(1^{n_{k}},\omega,\pi)=z]\geq
2/3\qquad\text{and}\qquad\Pr[V(1^{n_{k}},\pi,\omega)=z]\geq 2/3,$ where the
probabilities are over the internal randomness of $V$.

In more detail, if $k<t$, then $V$ treats $\pi_{1}$ and $\pi_{2}$ as inputs to
the circuit $\mathsf{GGM}_{T_{k+1}}[C_{n_{k+1}}]$, and let

$\hat{f}_{k+1}:=\mathsf{GGM}_{T_{k+1}}[C_{n_{k+1}}](\pi_{1})\quad\text{and}\quad\hat{g}_{k+1}:=\mathsf{GGM}_{T_{k+1}}[C_{n_{k+1}}](\pi_{2}).$

Here, the lengths of $\pi_{1}$ and $\pi_{2}$ are $\ell\coloneqq
n_{k+1}\leq\mathrm{poly}(n_{k})$. If $k=t$, then $V$ defines
$\hat{f}_{k+1}:=\pi_{1}$, $\hat{g}_{k+1}:=\pi_{2}$, and their lengths are
$\ell\coloneqq T_{t+1}\leq n_{k+1}\leq\mathrm{poly}(n_{k})$. It is intended
that one of the $\hat{f}_{k+1}$ and $\hat{g}_{k+1}$ is
$f_{k+1}=\widetilde{\mathsf{History}}(C_{n_{k}},f_{k})$ ($V$ needs to figure
out which one).

We now specify the intended proof $\omega\in\\{0,1\\}^{n_{k+1}}$. When $k<t$,
since $f_{k+1}\in\mathrm{Range}(\mathsf{GGM}_{T_{k+1}}[C_{n_{k+1}}])$, we can
set $\omega$ so that $\mathsf{GGM}_{T_{k+1}}[C_{n_{k+1}}](\omega)=f_{k+1}$.
When $k=t$, we simply set $\omega=f_{k+1}$.

Note that 3.2 provides us “random access” to the (potentially very long)
strings $\hat{f}_{k+1}$ and $\hat{g}_{k+1}$: (take $\hat{f}_{k+1}$ as an
example) given $\pi_{1}$ and $j\in\\{0,1,\dotsc,T_{k+1}-1\\}$, one can compute
the $j$-th bit of $\hat{f}_{k+1}$ in $\mathrm{poly}(n_{k})$ time. Also recall
from 5.5 that for each $i$,
$f_{i+1}=\widetilde{\mathsf{History}}(C_{n_{i}},f_{i})$ contains the string
$f_{i}$, which can be retrieved by the oracle algorithm $\mathsf{Input}$
described in Item 1 of 5.5. Therefore, for each $i$ from $k$ downto $1$, we
can recursively define $\hat{f}_{i}$ such that
$(\hat{f}_{i})_{j}=\mathsf{Input}_{T_{i},n_{i}}^{\hat{f}_{i+1}}(j)$ (similarly
for $\hat{g}_{i}$). We also define $\hat{f}_{0}$ and $\hat{g}_{0}$ to be the
concatenation of all length-$(2n_{0})$ strings in the lexicographical order,
so $\hat{f}_{0}=\hat{g}_{0}=f_{0}$.

Applying the algorithm $\mathsf{Input}$ recursively, we obtain two algorithms
$F$ and $G$ (depending on $\pi_{1}$ and $\pi_{2}$, respectively) that given
$i\in\\{0,1,\dotsc,k+1\\}$ and $j\in\\{0,1,\dotsc,T_{i}-1\\}$, output the
$j$-th bit of $\hat{f}_{i}$ or $\hat{g}_{i}$, respectively. Since
$\mathsf{Input}$ only makes one oracle query, these algorithms run in
$\mathrm{poly}(n_{k})$ time.

We are now ready to formally construct $V$. We first recursively define a
series of procedures $V_{0},\dotsc,V_{k+1}$, where each $V_{i}$ takes an input
$j$ and outputs (with high probability) the $j$-th bit of $f_{i}$. Let $V_{0}$
be the simple algorithm that, on input $j$, computes the $j$-th bit of
$f_{0}$. For every $i\in[k+1]$, we define

$V_{i}(\alpha)\coloneqq\mathsf{Select}_{T_{i-1},n_{i-1}}^{V_{i-1},\hat{f}_{i},\hat{g}_{i}}(C_{n_{i-1}},\alpha,\varepsilon_{i})$

for some $\varepsilon_{i}\in[0,1)$ to be specified later, where
$\mathsf{Select}$ is the algorithm in Item 2 of 5.5. We note that since
$V_{i-1}$ is a randomized algorithm, when $V_{i}$ calls $V_{i-1}$, it also
draws _independent_ random coins used by the execution of $V_{i-1}$. Moreover,
all calls to $\hat{f}_{i}$ and $\hat{g}_{i}$ in $V_{i}$ can be simulated by
calling our algorithms $F$ and $G$. Jumping ahead, we remark that $V_{i}$ is
supposed to compute $f_{i}$ when at least one of $\hat{f}_{i}$ or
$\hat{g}_{i}$ is $f_{i}$. We then set

$V(1^{n_{k}},\pi_{1},\pi_{2})\coloneqq\mathsf{Output}_{T_{k},n_{k}}^{V_{k+1}}$

(note that $V_{k+1}$ is defined from $\hat{f}_{k+1}$ and $\hat{g}_{k+1}$,
which are in turn constructed from $\pi_{1}$ and $\pi_{2}$), where
$\mathsf{Output}_{T_{k},n_{k}}$ is the algorithm from Item 1 of 5.5.

##### Correctness of $V$.

Let $\tau\in\mathbb{N}$ be a large constant such that $\mathsf{Select}_{T,n}$
runs in $(n\cdot\log 1/\varepsilon)^{\tau}$ time. In particular, on any input
$\alpha$,
$\mathsf{Select}_{T_{i-1},n_{i-1}}^{V_{i-1},\hat{f}_{i},\hat{g}_{i}}(C_{n_{i-1}},\alpha,\varepsilon_{i})$
makes at most $(n_{i-1}\cdot\log 1/\varepsilon_{i})^{\tau}$ many queries to
$V_{i-1}$.

We say $\mathsf{Select}^{f,\pi_{1},\pi_{2}}_{T,n}(C,\alpha,\varepsilon_{i})$
makes an error if the following statements hold
($h=\widetilde{\mathsf{History}}(C,f)$ from 5.5):363636The condition below
only applies when at least one of $\pi_{1}$ and $\pi_{2}$ is $h$. If neither
of them are $h$, then $\mathsf{Select}$ by definition never errs.

$\left[\pi_{1}=h\quad\mathsf{OR}\quad\pi_{2}=h\right]\quad\mathsf{AND}\quad\left[\mathsf{Select}^{f,\pi_{1},\pi_{2}}_{T,n}(C_{n_{i-1}},\alpha,\varepsilon_{i})\neq
h_{\alpha}\right].$

Similarly, we say that
$\mathsf{Select}_{T_{i-1},n_{i-1}}^{V_{i-1},\hat{f}_{i},\hat{g}_{i}}(C_{n_{i-1}},\alpha,\varepsilon_{i})$
makes an error if either (1) one of the queries to $V_{i-1}$ are incorrectly
answered (i.e., the answer is not consistent with $f_{i-1}$) or (2) all
queries are correctly answered but
$\mathsf{Select}_{T_{i-1},n_{i-1}}^{f_{i-1},\hat{f}_{i},\hat{g}_{i}}(C_{n_{i-1}},\alpha,\varepsilon_{i})$
makes an error. Note that (2) happens with probability at most
$\varepsilon_{i}$ from Item 2 of 5.5.

Now we are ready to specify the parameter $\varepsilon_{i}$. We set
$\varepsilon_{k+1}=1/(100\cdot n_{k+1})$, and for every
$i\in\\{0,1,\dotsc,k\\}$, we set

$\varepsilon_{i}=\frac{\varepsilon_{i+1}}{4\cdot(n_{i}\cdot\log
1/\varepsilon_{i+1})^{\tau}}.$

To show the correctness of $V$, we prove the following claim by induction.

######  Claim 5.8.

Assume either $\hat{f}_{k+1}=f_{k+1}$ or $\hat{g}_{k+1}=f_{k+1}$. For every
$i\in\\{0,1,\dotsc,k+1\\}$ and $\alpha\in\left[|f_{i}|\right]$,
$V_{i}(\alpha)$ outputs $f_{i}(\alpha)$ with probability at least
$1-2\varepsilon_{i}$.

###### Proof.

The claim certainly holds for $V_{0}$. Now, for $i\in[k+1]$, assuming it holds
for $V_{i-1}$, it follows that
$\mathsf{Select}_{T_{i-1},n_{i-1}}^{V_{i-1},\hat{f}_{i},\hat{g}_{i}}(C_{n_{i-1}},\alpha,\varepsilon_{i})$
makes an error with probability at most

$\varepsilon_{i}+(n_{i-1}\cdot\log 1/\varepsilon_{i})^{\tau}\cdot
2\varepsilon_{i-1}\leq 2\varepsilon_{i}.$

By the definition of making an error and our assumption that either
$\hat{f}_{k+1}=f_{k+1}$ or $\hat{g}_{k+1}=f_{k+1}$ (from which we know either
$\hat{f}_{i}=f_{i}$ or $\hat{g}_{i}=f_{i}$), it follows that $V_{i}(\alpha)$
outputs $f_{i}(\alpha)$ with probability at least $1-2\varepsilon_{i}$. ∎

Note that $\mathsf{Output}_{T_{k},n_{k}}^{V_{k+1}}$ makes at most $4n_{k}$
queries to $V_{k+1}$. It follows from 5.8 that when either
$\hat{f}_{k+1}=f_{k+1}$ or $\hat{g}_{k+1}=f_{k+1}$, we have that
$V(1^{n_{k}},\pi_{1},\pi_{2})$ outputs $z$ with probability at least
$1-(4n_{k})\cdot 1/(100n_{k+1})\geq 2/3$. The correctness of $V$ then follows
from our choice of $\omega$.

##### Running time of $V$.

Finally, we analyze the running time of $V$, for which we first need to bound
$\log\varepsilon_{i}^{-1}$. First, we have

$\log\varepsilon_{k+1}^{-1}=\log n_{k+1}+\log 100.$

By our definition of $\varepsilon_{i}$ and the fact that $\tau$ is a constant,
we have

$\displaystyle\log\varepsilon_{i}^{-1}$
$\displaystyle=\log\varepsilon_{i+1}^{-1}+\log 4+\tau\cdot\left(\log
n_{i}+\log\log\varepsilon_{i+1}^{-1}\right)$ $\displaystyle\leq
2\log\varepsilon_{i+1}^{-1}+O(\log n_{i}).$

Expanding the above and noting that $k\leq t\leq O(\log n_{0})$, for every
$i\in[k+1]$ we have that

$\log\varepsilon_{i}^{-1}\leq 2^{k}\cdot O\left(\sum_{\ell=0}^{k}\log
n_{\ell}\right)\leq\mathrm{poly}(n_{0})\cdot\log n_{k}.$

Now we are ready to bound the running time of the $V_{i}$. First $V_{0}$ runs
in $T_{0}=\mathrm{poly}(n_{0})$ time. For every $i\in[k+1]$, by the definition
of $V_{i}$, we know that $V_{i}$ runs in time

$T_{i}=O\Big{(}(n_{i-1}\cdot\log
1/\varepsilon_{i})^{\tau}\Big{)}\cdot(T_{i-1}+n_{k}^{\beta}+1),$

where $\beta$ is a sufficiently large constant and $n_{k}^{\beta}$ bounds the
running time of answering each query
$\mathsf{Select}_{T_{i-1},n_{i-1}}^{V_{i-1},\hat{f}_{i},\hat{g}_{i}}(C_{n_{i-1}},\alpha,\varepsilon_{i})$
makes to $\hat{f}_{i}$ or $\hat{g}_{i}$, by running $F$ or $G$, respectively.

Expanding out the bound for $T_{k}$, we know that $V_{k+1}$ runs in time

$2^{O(k)}\cdot\left(\mathrm{poly}(n_{0})\cdot\log
n_{k}\right)^{O(k\cdot\tau)}\cdot
n_{k}^{\beta}\cdot\prod_{i=1}^{k+1}n_{i-1}^{\tau}.$

Since $n_{k}=n_{0}^{10^{k}}$ and $k\leq O(\log n_{0})$, the above can be