Range Avoidance and Remote Point:
New Algorithms and Hardness

For a constant depth unbounded fan-in circuit class $𝒞$, we establish a tight equivalence between the complexity of solving $𝒞$-$\text{Avoid}[n,n^{1+\epsilon }]$ in ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}}$ and proving exponential lower bounds for $𝒞$ circuits against ${𝐄}^{\mathrm{𝐍𝐏}}$, generalizing the reduction of Jeřábek and Korten [23, 28], who proved that $\text{Avoid}\in {\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}}$ if and only if ${𝐄}^{\mathrm{𝐍𝐏}}\not\subset i.o.\text{-}\mathrm{𝖲𝖨𝖹𝖤}[2^{o(n)}]$¹²¹²12This reduction, which we refer to as Jeřábek -Korten reduction, was originally proved in the framework of bounded arithmetic by Jeřábek [23], and later translated to the language of computational complexity by Korten [28]. Specifically, as pointed out to us by Erfan Khaniki, [23, Proposition 3.5] proved that the dual weak pigeonhole principle ($\mathrm{dwPHP}(\mathrm{𝖯𝖵})$) is equivalent to the statement asserting the existence of Boolean functions with exponential circuit complexity in Buss’ bounded arithmetic theory ${𝖲}_2^1$ which captures polynomial time reasoning. An ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}}$ algorithm for Avoid can be extracted from the dual weak pigeonhole principle (i.e., formalization of the totality of Avoid) in ${𝖲}_2^1$ via the Witnessing Theorem from [30]..

The forward direction – namely, that an ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}}$ algorithm for $𝒞$-Avoid implies exponential $𝒞$ circuit lower bounds against ${𝐄}^{\mathrm{𝐍𝐏}}$ – was largely established in [36]. A key component of this argument is the universality property of the circuit class $𝒞$: that the truth table generator ${\mathrm{𝖳𝖳}}_{𝒞}$ can itself be computed by a circuit in $𝒞$. We strengthen and formalize this notion, showing that any circuit class $𝒞$ containing ${\mathrm{𝖠𝖢}}^0$ satisfies this property. The intuition is that the universal circuit $𝒰$ acts as a decoder: given an encoding of a circuit $C$ and an input $x$, it decodes $C$ and evaluates it on $x$. Since decoding and simple simulation can be implemented in ${\mathrm{𝖠𝖢}}^0$, this universality follows for all such classes.

The reverse direction, which shows that exponential $𝒞$ circuit lower bounds for functions in ${𝐄}^{\mathrm{𝐍𝐏}}$ imply that $𝒞$-$\text{Avoid}\in {\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}}$, proceeds by generalizing Korten’s construction based on the GGM-tree. We illustrate the approach in the context of ${\mathrm{𝖠𝖢}}^0$-$\text{Avoid}[n,n^{1+\epsilon }]$, although the framework extends to the broader $𝒞$-$\text{Remote-Point}[n,n^{1+\epsilon }]$ problem for any $𝒞$ containing ${\mathrm{𝖠𝖢}}^0$.

We first briefly recall the ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}}$ reduction from circuit lower bound to Avoid in [23, 28] which we thereafter refer to as Jeřábek -Korten reduction. Given an instance of $\text{Avoid}[n,2n]$, which we call $C$, one constructs a new circuit $\mathrm{𝖦𝖦𝖬}[C]$ by composing $C$ along the nodes of a perfect binary tree of height $k$ (this construction is known as the GGM-tree construction). The resulting circuit has stretch $n\cdot 2^k$, and the output $y\in \mathrm{Range}(\mathrm{𝖦𝖦𝖬}[C])$ can be regarded as encoding the truth table of a function $g$, whose input is the bits used to select a path in the tree. Importantly, due to redundancy and the tree structure in $\mathrm{𝖦𝖦𝖬}[C]$, this output $y$ can be computed by a relatively small-size circuit at the cost of increasing the depth. Thus, the complexity of the function $g$ – whose truth table is $y$ – can be bounded in terms of the complexity of $C$ and the structure of the GGM-tree.

We generalize this framework in the following three aspects: (1) the fan-out of the tree, denoted by $q$; (2) the height of the tree, denoted by $k$; and (3) the circuit $C$, which we draw from a restricted circuit class $𝒞$.

Let $\mathrm{\ell }$ denote the stretch of the resulting circuit after composing $C$ through the generalized GGM-tree, which we denote by ${\mathrm{𝖦𝖦𝖬}}_{\mathrm{\ell },q,k}[C]$ (see Figure 1 for an illustration). It is easy to see that $\mathrm{\ell }=n\cdot q^k$. To analyze the complexity of any $y\in \mathrm{Range}({\mathrm{𝖦𝖦𝖬}}_{\mathrm{\ell },q,k}[C])$, we associate it with a function $g:{\{0,1\}}^{\log \mathrm{\ell }}\to \{0,1\}$ (corresponding to the structure of the GGM-tree), whose truth table is exactly $y$.

The circuit computing $g$ can be constructed by composing the circuit $C$ with $k$ layers of multiplexing (selection) and a final indexing operation. These multiplexing and indexing subcircuits can be implemented by $O(n)$-size $\mathrm{𝖣𝖭𝖥}$ formulas, and hence belong to any class containing $\mathrm{𝖣𝖭𝖥}$ (such as ${\mathrm{𝖠𝖢}}^0$).

Assuming $C\in {\mathrm{𝖠𝖢}}_d^0$ where ${\mathrm{𝖠𝖢}}_d^0$ denotes depth $d$ ${\mathrm{𝖠𝖢}}^0$ circuits, to ensure that $g\in {\mathrm{𝖠𝖢}}^0$, we must take $k=O(1)$. By setting the fan-out $q=n^{\epsilon }$, the overall stretch becomes $\mathrm{\ell }=n\cdot n^{k\epsilon }=n^{1+k\epsilon }$, and the resulting circuit $g$ has size $O(n)+O(|C|\cdot k)=O(n^{1+\epsilon })$.

Now suppose there exists a function $f\in {𝐄}^{\mathrm{𝐍𝐏}}$ that requires ${\mathrm{𝖠𝖢}}_{dk}^0$ circuits of size at least ${\mathrm{\ell }}^{\gamma }$ for some constant $\gamma \in (0,1)$. Then for sufficiently large $\mathrm{\ell }$, $f$ cannot be in the range of ${\mathrm{𝖦𝖦𝖬}}_{\mathrm{\ell },q,k}[C]$, since all such $y$ have low circuit complexity. Thus, we can use $f$ to find a string not in $\mathrm{Range}(C)$ by traversing the GGM-tree with an $\mathrm{𝐍𝐏}$ oracle backwards. This yields an ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}}$ algorithm for ${\mathrm{𝖠𝖢}}_d^0$-$\text{Avoid}[n,nq]$, completing the reduction.

Altogether, this establishes a precise characterization:

for any $𝒞$ containing ${\mathrm{𝖠𝖢}}^0$, and where the stretch satisfies $nq=n^{1+\epsilon }$ for any arbitrary constant $\epsilon >0$.

We try to extend the GGM-style idea to Remote-Point. Nevertheless, the original $\mathrm{𝖩𝖾}\check{𝗋}\acute{𝖺}\mathrm{𝖻𝖾𝗄}$-$\mathrm{𝖪𝗈𝗋𝗍𝖾𝗇}$ reduction does not work for Remote-Point. Consider the toy case of ${\mathrm{𝖦𝖦𝖬}}_{4n,2,2}[C]$. Assume that we have an average-case hard truth table $y$ and are not able to find a remote point of $C$ at relative distance $\rho$ by traversing down the tree. Divide $y$ into two blocks $y_1,y_2$, each of size $2n$. Then there exists $x,x_1,x_2\in {\{0,1\}}^n$ such that $C(x_1){\approx }_{\rho }{y}_1$, $C(x_2){\approx }_{\rho }{y}_2$, and $C(x){\approx }_{\rho }(x_1\circ x_2)$, where $C(x_1),C(x_2)$, and $C(x)$ respectively achieve the maximum distance from $y_1$, $y_2$, and $x_1\circ x_2$ among all points in $\mathrm{Range}(C)$. However, dividing $C(x)$ into two blocks of equal size $x_1^{\prime }$ and $x_2^{\prime }$, it is unclear how close $C(x_1^{\prime })$ is to $C(x_1)$ and how close $C(x_2^{\prime })$ is to $C(x_2)$. In other words, it is hard to argue about the distance between $y$ and ${\mathrm{𝖦𝖦𝖬}}_{4n,2,2}[C](x)$.

To solve this problem, we use an idea from [8] that reduces Remote-Point to Avoid, and incorporate an error-correcting code at each node of the GGM-tree to prevent the accumulation of errors across levels. To illustrate the core idea, consider first the simpler case of a code with unique decoding. Suppose at each node, we compose the circuit $C:{\{0,1\}}^n\to {\{0,1\}}^m$ with a unique decoder ${\mathrm{𝖣𝖾𝖼}}_{\mathrm{𝗎𝗇𝗂𝗊}}:{\{0,1\}}^m\to {\{0,1\}}^{qn}$ for a code with decoding radius $\rho$. If a string $y\in {\{0,1\}}^{qn}$ is not in $\mathrm{Range}({\mathrm{𝖣𝖾𝖼}}_{\mathrm{𝗎𝗇𝗂𝗊}}\circ C)$, then its encoding $\mathrm{𝖤𝗇𝖼}(y)$ (under the code’s natural encoding) is at least $\rho$-far from $\mathrm{Range}(C)$. This property effectively isolates the error at each node: the failure to find a preimage of $y$ under ${\mathrm{𝖣𝖾𝖼}}_{\mathrm{𝗎𝗇𝗂𝗊}}\circ C$ directly implies that $y$ is a remote-point for $C$, without the error propagating to its children. This allows the reduction to proceed similarly to the Avoid problem, by searching for a preimage on each node of the tree.

However, unique decoding limits us to a radius of $\rho \le 1/4-\epsilon$, which is insufficient for our purposes. In the actual construction, we employ list-decoding to achieve a larger radius of $\rho =1/2-\epsilon$. We use a list-decodable code with a decoder ${\mathrm{𝖣𝖾𝖼}}_{\mathrm{𝗅𝗂𝗌𝗍}}:{\{0,1\}}^m\to {({\{0,1\}}^{qn})}^L$. At each node, applying ${\mathrm{𝖣𝖾𝖼}}_{\mathrm{𝗅𝗂𝗌𝗍}}\circ C$ produces a list of candidate values. We then apply a padding method to pad both the input and the output of $C$ with extra $\log L$ bits. This enables us to select one candidate from this list to pass to the next level of the tree.

Hence we get a conditional ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}}$ for Remote-Point. Combining with a refinement of the result in [36] (Theorem 2.8), it yields an equivalence between the ${\mathrm{𝐅𝐏}}^{\mathrm{𝐍𝐏}}$ algorithm for Remote-Point and the average-case circuit lower bound for ${𝐄}^{\mathrm{𝐍𝐏}}$.

We present the first subexponential-time algorithm for ${\mathrm{𝖭𝖢}}_k^0$-$\text{Avoid}[n,n^{1+\epsilon }]$, achieving runtime $2^{n^{1-\frac{\epsilon }{k-1}+o(1)}}$ for any $\epsilon >0$. Our approach exploits structural limitations of local circuits in terms of their associated bipartite graphs to identify small subcircuits with poor expansion, enabling targeted enumeration over their input-output behavior.

The algorithm is based on the following high-level idea: every ${\mathrm{𝖭𝖢}}_k^0[n,n^{1+\epsilon }]$ circuit corresponds to a degree-$k$ left-regular bipartite graph with $n$ right vertices (inputs) and $m=n^{1+\epsilon }$ left vertices (outputs). Using standard probabilistic methods, one can show that a random left-regular bipartite graph with degree $k$, $n$ right vertices and $m(n)=n^{1+\epsilon }$ left vertices is a $(K=o(n),A=1-o(1))$ vertex expander – meaning that for every subset of left vertices of size $\le K$, it has $\ge KA$ neighbors. One would expect these probabilistic arguments to be actually tight. Assuming so, we would be able to find a Hall-violating subsets (i.e., a subset of outputs whose neighbors have size smaller than the subset of outputs) in any such graphs.

Luckily, the lower bound results on disperser graphs from [35] can be adapted to argue that such graphs necessarily contain Hall-violating subsets of outputs of size at most $K=n^{1-\frac{\epsilon }{k-1}+o(1)}$. This means that every such circuit contains a subcircuit of size $K$ that maps a subset of inputs to outputs non-surjectively.

Our algorithm proceeds by brute-force search for such Hall-violating subsets $S\subseteq [m]$ of size $K$. Once a violating subset is found, we isolate the corresponding subcircuit $C^{\prime }$ of size $K$, and enumerate all strings in ${\{0,1\}}^{|\mathrm{\Gamma }(S)|}$ to find those not in the image of $C^{\prime }$. We then lift these local non-image strings to full-length output strings by assigning arbitrary values outside of $S$, yielding many globally valid strings not in the image of the full circuit $C$.

This gives the following guarantee: for every ${\mathrm{𝖭𝖢}}_k^0[n,n^{1+\epsilon }]$ circuit, we can find (and succinctly represent) at least $2^{n^{1+\epsilon }-1}$ strings outside the range of the circuit in time

Under a conjectured tight bound on bipartite dispersers, we further refine this analysis to show that even smaller Hall-violating subsets exist, yielding improved runtimes of $2^{n^{1-\frac{\epsilon }{k-2}+o(1)}}$. Notably, this leads to polynomial-time algorithms for ${\mathrm{𝖭𝖢}}_k^0$-Avoid in stretch regimes as low as $m=n^{k-1}/{\log }^{k-2}n$, improving a prior work [13] which required larger stretch.

Finally, we connect our algorithmic result to pseudorandomness. We show that any subexponential-time Avoid algorithm capable of identifying a non-negligible fraction of non-image strings for ${\mathrm{𝖭𝖢}}_k^0$ circuits contradicts the existence of secure ${\mathrm{𝖭𝖢}}_k^0$-based pseudorandom generators (PRGs) against subexponential-time adversary. In particular, under standard assumptions about local PRGs, our algorithm demonstrates that no such PRG with stretch $n^{1+\epsilon }$ can be secure against $2^{n^{\gamma }}$-time distinguishers for any $\gamma \ge 1-\frac{\epsilon }{k-1}+o(1)$, even with constant distinguishing advantage.

We design a greedy, local algorithm for solving ${\mathrm{𝖭𝖢}}_k^0$-$\text{Avoid}[n,n+1]$ that proceeds by iteratively fixing output bits to values that provably shrink the preimage space of the circuit. At each step, the algorithm selects an unfixed output bit $y_i$ and assigns it a value such that the number of inputs consistent with all fixed output values decreases by at least a factor of $1/2$. This ensures that after at most $n+1$ such assignments, the preimage space collapses to an empty set, yielding a string outside the image of the circuit.

The core technical challenge lies in bounding the “decision space”, i.e., the portion of the input space that must be explored to determine the effect of fixing an output bit. We analyze this by modeling the ${\mathrm{𝖭𝖢}}_k^0$ circuit as a bipartite dependency graph between input and output bits, and we introduce the notion of the traversed space: the subset of input variables affected by the fixed output bits. We show that after fixing $t$ output bits, the maximum size of any connected component (i.e., subspace) in the traversed space is bounded by $2^{(k-2)t+1}$. This follows from structural properties of bounded-locality circuits and a case-based inductive argument.

Combining this with the observation that fixing each output bit reduces the entropy of the input space by one, we find that the decision space remains small as long as $t\le n/(k-1)$. In particular, the algorithm only needs to examine subspaces of size at most

leading to a total runtime of $O(n\cdot 2^{(k-2)n/(k-1)})$. Notably, when $k=2$, the runtime becomes linear, reproducing the result of [15]. For larger $k$, this provides a non-trivial improvement over brute force.

We also show a matching lower bound for this greedy strategy: under mild assumptions on the structure of random ${\mathrm{𝖭𝖢}}_k^0$ circuits (specifically, that they form good bipartite vertex expanders), any such greedy algorithm necessarily explores an exponential-sized decision space in the worst case. This demonstrates that while the algorithm performs well for $k=2$, solving ${\mathrm{𝖭𝖢}}_k^0$-Avoid efficiently in the general case may require fundamentally different techniques.