The Range Avoidance ($\text{Avoid}$) problem $\mathcal{C}$-$\text{Avoid}[n,m(n)]$ asks that, given a circuit in a class $\mathcal{C}$ with input length $n$ and output length $m(n)>n$, find a string not in the range of the circuit. This problem has been a central piece in several recent frameworks for proving circuit lower bounds and constructing explicit combinatorial objects. Previous works by Korten (FOCS' 21) and Ren, Santhanam, and Wang (FOCS' 22) showed that algorithms for $\text{Avoid}$ are closely related to circuit lower bounds. In particular, Korten's work reinterpreted an earlier result in bounded arithmetic, originally proved by Je?ábek (Ann. Pure Appl. Log. 2004), as an equivalence in computational complexity between the existence of $\mathbf{FP}^\mathbf{NP}$ algorithms for the general $\text{Avoid}$ problem and $2^{\Omega(n)}$ lower bounds against general Boolean circuits for the class $\mathbf{E}^\mathbf{NP}$. In this work, we significantly complement these works by generalizing the equivalence result to restricted circuit classes and obtain the following:

(1) For any constant depth unbounded fan-in circuit class $\mathcal{C}\supseteq \mathrm{AC}^0$, there is an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\mathcal{C}$-$\text{Avoid}[n,n^{1+\varepsilon}]$ (for any constant $\varepsilon>0$) if and only if $\mathbf{E}^\mathbf{NP}$ cannot be computed by $\mathcal{C}$ circuits of size $2^{o(n)}$. This addresses an open problem by Korten (Bulletin of EATCS' 25).

(2) If $\mathbf{E}^\mathbf{NP}$ cannot be computed by $o(2^n/n)$ size formulas, then there is an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\mathrm{NC}^0$-\textsc{Avoid}$[n,2n]$. Note that by an extension of Ren, Santhanam, and Wang (FOCS' 22), an $\FP^\mathbf{NP}$ algorithm for $\mathrm{NC}^0_4$-$\text{Avoid}[n,n+n^\delta]$ for any constant $\delta\in (0,1)$ implies $\mathbf{E}^\mathbf{NP}$ cannot be computed by $o(2^n/n)$ size formulas.

These results yield the first characterizations of $\mathbf{FP}^\mathbf{NP}$ $\mathcal{C}$-\text{Avoid} algorithms for low-complexity circuit classes such as $\mathrm{AC}^0$.

We also consider the average-case analog of \textsc{Avoid}, the Remote Point ($\text{Remote-Point}$) problem, and establish:
(1) For some suitable function $c(n)$ and constant $\gamma > 0$, there is an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\RemotePoint[n,n^{6+\gamma},c(O_{\gamma}(\log n))]$ if and only if $\mathbf{E}^\mathbf{NP}$ cannot be $(1/2-c(n))$-approximated by circuits of size $2^{o(n)}$.

Finally, we also present two improved algorithms for $\mathrm{NC}^0$-$\text{Avoid}$:
(1) A family of $2^{n^{1-\frac{\varepsilon}{k-1}+o(1)}}$ time algorithms for $\mathrm{NC}^0_k$-$\text{Avoid}[n,n^{1+\varepsilon}]$ for any $\varepsilon>0$, exhibiting the first subexponential-time algorithm for any super-linear stretch.
(2) Faster local algorithms for $\mathrm{NC}^0_k$-$\text{Avoid}[n,n+1]$ running in time $O(n2^{\frac{k-2}{k-1}n})$, improving the naive $2^n\cdot \mathrm{poly}(n)$ bound.

1. Add the constraint of "constant-depth" to the equivalence regarding exponential circuit lower bounds and circuit range avoidance.
2. Change the near-equivalence result to be with respect to formulas instead of NC^1 circuits, since an NC^1 (NC^i) circuit has size at most polynomial (quasipolynomial) by its definition.
3. Give the correct proof regarding the equivalence between remote point and average-case circuit lower bounds. Currently, the equivalence only works for P/poly.

The Range Avoidance ($\text{Avoid}$) problem $\mathcal{C}$-$\text{Avoid}[n,m(n)]$ asks that, given a circuit in a class $\mathcal{C}$ with input length $n$ and output length $m(n)>n$, find a string not in the range of the circuit. This problem has been a central piece in several recent frameworks for proving circuit lower bounds and constructing explicit combinatorial objects. Previous works by Korten (FOCS' 21) and Ren, Santhanam, and Wang (FOCS' 22) showed that algorithms for $\text{Avoid}$ are closely related to circuit lower bounds. In particular, Korten's work reinterpreted an earlier result in bounded arithmetic, originally proved by Je?ábek (Ann. Pure Appl. Log. 2004), as an equivalence in computational complexity between the existence of $\mathbf{FP}^\mathbf{NP}$ algorithms for the general $\text{Avoid}$ problem and $2^{\Omega(n)}$ lower bounds against general Boolean circuits for the class $\mathbf{E}^\mathbf{NP}$. In this work, we significantly complement these works by generalizing the equivalence result to restricted circuit classes and obtain the following:

(1) For any constant depth unbounded fan-in circuit class $\mathcal{C}\supseteq \mathsf{AC}^0$, there is an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\mathcal{C}$-$\text{Avoid}[n,n^{1+\varepsilon}]$ (for any constant $\varepsilon>0$) if and only if $\mathbf{E}^\mathbf{NP}$ cannot be computed by $\mathcal{C}$ circuits of size $2^{o(n)}$. This addresses an open problem by Korten (Bulletin of EATCS' 25).

(2) If $\mathbf{E}^\mathbf{NP}$ cannot be computed by $o(2^n/n)$ size formulas, then there is an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\mathsf{NC}^0$-\textsc{Avoid}$[n,2n]$. Note that by an extension of Ren, Santhanam, and Wang (FOCS' 22), an $\FP^\mathbf{NP}$ algorithm for $\NC^0_4$-$\text{Avoid}[n,n+n^\delta]$ for any constant $\delta\in (0,1)$ implies $\mathbf{E}^\mathbf{NP}$ cannot be computed by $o(2^n/n)$ size formulas.

These results yield the first characterizations of $\mathbf{FP}^\mathbf{NP}$ $\mathcal{C}$-\text{Avoid} algorithms for low-complexity circuit classes such as $\mathsf{AC}^0$.

We also consider the average-case analog of \textsc{Avoid}, the Remote Point ($\text{Remote-Point}$) problem, and establish:
(1) For some suitable function $c(n)$ and constant $\gamma > 0$, there is an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\RemotePoint[n,n^{6+\gamma},c(O_{\gamma}(\log n))]$ if and only if $\mathbf{E}^\mathbf{NP}$ cannot be $(1/2-c(n))$-approximated by circuits of size $2^{o(n)}$.

Finally, we also present two improved algorithms for $\mathsf{NC}^0$-$\text{Avoid}$:
(1) A family of $2^{n^{1-\frac{\varepsilon}{k-1}+o(1)}}$ time algorithms for $\mathsf{NC}^0_k$-$\text{Avoid}[n,n^{1+\varepsilon}]$ for any $\varepsilon>0$, exhibiting the first subexponential-time algorithm for any super-linear stretch.
(2) Faster local algorithms for $\mathsf{NC}^0_k$-$\text{Avoid}[n,n+1]$ running in time $O(n2^{\frac{k-2}{k-1}n})$, improving the naive $2^n\cdot \mathrm{poly}(n)$ bound.

1. Add the constraint of "constant-depth" to the equivalence regarding exponential circuit lower bounds and circuit range avoidance.
2. Change the near-equivalence result to be with respect to formulas instead of NC^1 circuits, since an NC^1 (NC^i) circuit has size at most polynomial (quasipolynomial) by its definition.
3. Give the correct proof regarding the equivalence between remote point and average-case circuit lower bounds. Currently, the equivalence only works for P/poly.

The Range Avoidance ($\text{Avoid}$) problem $\mathcal{C}$-$\text{Avoid}[n,m(n)]$ asks that, given a circuit in a class $\mathcal{C}$ with input length $n$ and output length $m(n)>n$, find a string not in the range of the circuit. This problem has been a central piece in several recent frameworks for proving circuit lower bounds and constructing explicit combinatorial objects. Previous works by Korten (FOCS' 21) and Ren, Santhanam, and Wang (FOCS' 22) showed that algorithms for $\text{Avoid}$ are closely related to circuit lower bounds. In particular, Korten's work reinterpreted an earlier result in bounded arithmetic, originally proved by Je?ábek (Ann. Pure Appl. Log. 2004), as an equivalence in computational complexity between the existence of $\mathbf{FP}^\mathbf{NP}$ algorithms for the general $\text{Avoid}$ problem and $2^{\Omega(n)}$ lower bounds against general Boolean circuits for the class $\mathbf{E}^\mathbf{NP}$. In this work, we significantly complement these works by generalizing the equivalence result to restricted circuit classes and obtain the following:

(1) For any constant depth unbounded fan-in circuit class $\mathcal{C}\supseteq \mathsf{AC}^0$, there is an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\mathcal{C}$-$\text{Avoid}[n,n^{1+\varepsilon}]$ (for any constant $\varepsilon>0$) if and only if $\mathbf{E}^\mathbf{NP}$ cannot be computed by $\mathcal{C}$ circuits of size $2^{o(n)}$. This addresses an open problem by Korten (Bulletin of EATCS' 25).

(2) If $\mathbf{E}^\mathbf{NP}$ cannot be computed by $o(2^n/n)$ size formulas, then there is an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\mathsf{NC}^0$-\textsc{Avoid}$[n,2n]$. Note that by an extension of Ren, Santhanam, and Wang (FOCS' 22), an $\FP^\mathbf{NP}$ algorithm for $\NC^0_4$-$\text{Avoid}[n,n+n^\delta]$ for any constant $\delta\in (0,1)$ implies $\mathbf{E}^\mathbf{NP}$ cannot be computed by $o(2^n/n)$ size formulas.

These results yield the first characterizations of $\mathbf{FP}^\mathbf{NP}$ $\mathcal{C}$-\text{Avoid} algorithms for low-complexity circuit classes such as $\mathsf{AC}^0$.

We also consider the average-case analog of \textsc{Avoid}, the Remote Point ($\text{Remote-Point}$) problem, and establish:
(1) For some suitable function $c(n)$ and constant $\gamma > 0$, there is an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\RemotePoint[n,n^{6+\gamma},c(O_{\gamma}(\log n))]$ if and only if $\mathbf{E}^\mathbf{NP}$ cannot be $(1/2-c(n))$-approximated by circuits of size $2^{o(n)}$.

Finally, we also present two improved algorithms for $\mathsf{NC}^0$-$\text{Avoid}$:
(1) A family of $2^{n^{1-\frac{\varepsilon}{k-1}+o(1)}}$ time algorithms for $\mathsf{NC}^0_k$-$\text{Avoid}[n,n^{1+\varepsilon}]$ for any $\varepsilon>0$, exhibiting the first subexponential-time algorithm for any super-linear stretch.
(2) Faster local algorithms for $\mathsf{NC}^0_k$-$\text{Avoid}[n,n+1]$ running in time $O(n2^{\frac{k-2}{k-1}n})$, improving the naive $2^n\cdot \mathrm{poly}(n)$ bound.

1. Add the constraint of "constant-depth" to the equivalence regarding exponential circuit lower bounds and circuit range avoidance.
2. Change the near-equivalence result to be with respect to formulas instead of NC^1 circuits, since an NC^1 (NC^i) circuit has size at most polynomial (quasipolynomial) by its definition.
3. Give the correct proof regarding the equivalence between remote point and average-case circuit lower bounds. Currently, the equivalence only works for P/poly.

The Range Avoidance (\text{Avoid}) problem $\mathscr{C}$-\text{Avoid}$[n,m(n)]$ asks that, given a circuit in a class $\mathscr{C}$ with input length $n$ and output length $m(n)>n$, find a string not in the range of the circuit. This problem has been a central piece in several recent frameworks for proving circuit lower bounds and constructing explicit combinatorial objects. Previous work by Korten (FOCS' 21) and by Ren, Santhanam, and Wang (FOCS' 22) showed that algorithms for \text{Avoid} are closely related to circuit lower bounds. In particular, Korten’s work reinterpreted an earlier result from bounded arithmetic, originally proved by \Jerabek (Ann.\;Pure\;Appl.\;Log.\;2004), as an equivalence in computational complexity between the existence of $\mathbf{FP}^\mathbf{NP}$ algorithms for the general \text{Avoid} problem and $2^{\Omega(n)}$ lower bounds against general Boolean circuits for the class $\mathbf{E}^\mathbf{NP}$. In this work, we significantly complement these works by generalizing the equivalence result to restricted circuit classes and obtain the following:
1. For any constant depth unbounded fan-in circuit class $\mathscr{C}\supseteq \mathsf{AC}^0$, there is an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\mathscr{C}$-$\Avoid[n,n^{1+\varepsilon}]$ (for any constant $\varepsilon>0$) if and only if $\mathbf{E}^\mathbf{NP}$ cannot be computed by $\mathscr{C}$ circuits of size $2^{o(n)}$. This addresses an open problem by Korten (Bulletin of EATCS' 25).
2. If $\E^\NP$ cannot be computed by $o(2^n/n)$ size formulas, then there is an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\mathsf{NC}^0$-\textsc{Avoid}$[n,2n]$. Note that by an extension of Ren, Santhanam, and Wang (FOCS' 22), an $\FP^\NP$ algorithm for $\NC^0_4$-$\Avoid[n,n+n^\delta]$ for any constant $\delta\in (0,1)$ implies $\E^\NP$ cannot be computed by $o(2^n/n)$ size formulas.

These results yield the first characterizations of $\mathbf{FP}^\mathbf{NP}$ $\mathscr{C}$-\textsc{Avoid} algorithms for low-complexity circuit classes such as $\mathsf{AC}^0$.

We also consider the average-case analog of \textsc{Avoid}, the Remote Point (\textsc{Remote-Point}) problem, and establish:
1. For some suitable function $c(n)$ and constant $\gamma > 0$, there is an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\RemotePoint[n,n^{6+\gamma},c(O_{\gamma}(\log n))]$ if and only if $\mathbf{E}^\mathbf{NP}$ cannot be $(1/2-c(n))$-approximated by circuits of size $2^{o(n)}$.

Finally, we also present two improved algorithms for $\mathsf{NC}^0$-$\Avoid$:
1. A family of $2^{n^{1-\frac{\varepsilon}{k-1}+o(1)}}$ time algorithms for $\mathsf{NC}^0_k$-\textsc{Avoid}$[n,n^{1+\varepsilon}]$ for any $\varepsilon>0$, exhibiting the first subexponential-time algorithm for any super-linear stretch.
2. Faster local algorithms for $\mathsf{NC}^0_k$-\textsc{Avoid}$[n,n+1]$ running in time $O(n2^{\frac{k-2}{k-1}n})$, improving the naive $2^n\cdot \mathrm{poly}(n)$ bound.

1. Add the constraint of "constant-depth" to the equivalence regarding exponential circuit lower bounds and circuit range avoidance.
2. Change the near-equivalence result to be with respect to formulas instead of NC^1 circuits, since an NC^1 (NC^i) circuit has size at most polynomial (quasipolynomial) by its definition.
3. Give the correct proof regarding the equivalence between remote point and average-case circuit lower bounds. Currently, the equivalence only works for P/poly.

The Range Avoidance ($\text{Avoid}$) problem $\mathcal{C}$-$\text{Avoid}[n,m(n)]$ asks that, given a circuit in a class $\mathcal{C}$ with input length $n$ and output length $m(n)>n$, find a string not in the range of the circuit. This problem has been a central piece in several recent frameworks for proving circuit lower bounds and constructing explicit combinatorial objects. Previous works by Korten (FOCS' 21) and Ren, Santhanam, and Wang (FOCS' 22) showed that algorithms for $\text{Avoid}$ are closely related to circuit lower bounds. In particular, Korten's work reinterpreted an earlier result in bounded arithmetic, originally proved by Je?ábek (Ann.\;Pure\;Appl.\;Log.\;2004), as an equivalence in computational complexity between the existence of $\mathbf{FP}^\mathbf{NP}$ algorithms for the general \text{Avoid} problem and $2^{\Omega(n)}$ lower bounds against general Boolean circuits for the class $\mathbf{E}^\mathbf{NP}$.

In this work, we significantly complement these works by generalizing the equivalence to restricted circuit classes and obtain the following:

(1) For any $\mathcal{C}\supseteq \mathrm{AC}^0$, there is an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\mathcal{C}$-$\text{Avoid}[n,n^{1+\varepsilon}]$ (for any constant $\varepsilon>0$) if and only if $\mathbf{E}^\mathbf{NP}$ cannot be computed by $\mathcal{C}$ circuits of size $2^{o(n)}$.
(2) For any integer $i$, if $\mathbf{E}^\mathbf{NP}$ cannot be computed by $o(2^n/n)$ size $\mathrm{NC}^{i+1}$ circuits, then there is an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\mathrm{NC}^i$-$\text{Avoid}[n,2n]$. Note that by an extension of Ren, Santhanam, and Wang (FOCS' 22), an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\mathrm{NC}^i$-$\text{Avoid}[n,n+n^\delta]$ for any constant $\delta\in (0,1)$ implies $\mathbf{E}^\mathbf{NP}$ cannot be computed by $o(2^n/n)$ size $\mathrm{NC}^{i+1}$ circuits.

These results yield the first characterizations of $\mathbf{FP}^\mathbf{NP}$ $\mathcal{C}$-$\text{Avoid}$ algorithms for low-complexity circuit classes such as $\mathrm{AC}^0$.
We also extend our results to the average-case analog of $\text{Avoid}$, the Remote Point ($\text{Remote-Point}$) problem, and establish similar equivalence between $\mathbf{FP}^\mathbf{NP}$ algorithms and the average-case circuit lower bounds for $\mathbf{E}^\mathbf{NP}$. Finally, we also present two improved algorithms for $\mathrm{NC}^0$-$\text{Avoid}$:
(1) A family of $2^{n^{1-\frac{\varepsilon}{k-1}+o(1)}}$ time algorithms for $\mathrm{NC}^0_k$-$\text{Avoid}[n,n^{1+\varepsilon}]$ for any $\varepsilon>0$, exhibiting the first subexponential-time algorithm for any super-linear stretch.
(2) Faster local algorithms for $\mathrm{NC}^0_k$-$\text{Avoid}[n,n+1]$ running in time $O(n2^{\frac{k-2}{k-1}n})$, improving the naive $2^n\cdot \mathrm{poly}(n)$ bound.

Minor revision to correct a historical inaccuracy: the $\mathbf{\FP}^{\mathbf{NP}}$ reduction from circuit lower bounds to algorithm for text{Avoid}, previously referred to as “Korten’s reduction,” was originally established in bounded arithmetic by Je?ábek (Ann. Pure Appl. Logic, 2004). We now refer to this as the “Je?ábek–Korten reduction” throughout the manuscript, and have added appropriate citations and acknowledgments. No technical content has changed.
Also changed few typos.

The Range Avoidance ($\text{Avoid}$) problem $\mathcal{C}$-$\text{Avoid}[n,m(n)]$ asks that, given a circuit in a class $\mathcal{C}$ with input length $n$ and output length $m(n)>n$, find a string not in the range of the circuit. This problem has been a central piece in several recent frameworks of proving circuit lower bounds and constructing explicit combinatorial objects. Previous works by Korten (FOCS' 21) and Ren, Santhanam, and Wang (FOCS' 22) showed that algorithms for $\text{Avoid}$ are closely related to circuit lower bounds. In particular, Korten's work established the equivalence between $\mathbf{FP}^\mathbf{NP}$ algorithms for general $\text{Avoid}$ and $2^{\Omega(n)}$ general boolean circuit lower bounds for the class $\mathbf{E}^\mathbf{NP}$. In this work, we significantly complement these works by generalizing Korten's result to restricted circuit classes, and obtaining the following:

(1) For any $\mathcal{C}\supseteq \mathrm{AC}^0$, there is an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\mathcal{C}$-$\text{Avoid}[n,n^{1+\varepsilon}]$ (for any constant $\varepsilon>0$) if and only if $\mathbf{E}^\mathbf{NP}$ cannot be computed by $\mathcal{C}$ circuits of size $2^{o(n)}$.
(2) For any integer $i$, if $\mathbf{E}^\mathbf{NP}$ cannot be computed by $o(2^n/n)$ size $\mathrm{NC}^{i+1}$ circuits, then there is an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\mathrm{NC}^i$-$\text{Avoid}[n,2n]$. Note that by an extension of Ren, Santhanam, and Wang (FOCS' 22), an $\mathbf{FP}^\mathbf{NP}$ algorithm for $\mathrm{NC}^i$-$\text{Avoid}[n,n+n^\delta]$ for any constant $\delta\in (0,1)$ implies $\mathbf{E}^\mathbf{NP}$ cannot be computed by $o(2^n/n)$ size $\mathrm{NC}^{i+1}$ circuits.

These results yield the first characterizations of $\mathbf{FP}^\mathbf{NP}$ $\mathcal{C}$-$\text{Avoid}$ algorithms for low-complexity circuit classes such as $\mathrm{AC}^0$.
We also extend our results to the average-case analog of $\text{Avoid}$, the Remote Point ($\text{Remote-Point}$) problem, and establish similar equivalence between $\mathbf{FP}^\mathbf{NP}$ algorithms and the average-case circuit lower bounds for $\mathbf{E}^\mathbf{NP}$. Finally, we also present two improved algorithms for $\mathrm{NC}^0$-$\text{Avoid}$:
(1) A family of $2^{n^{1-\frac{\varepsilon}{k-1}+o(1)}}$ time algorithms for $\mathrm{NC}^0_k$-$\text{Avoid}[n,n^{1+\varepsilon}]$ for any $\varepsilon>0$, exhibiting the first subexponential-time algorithm for any super-linear stretch.
(2) Faster local algorithms for $\mathrm{NC}^0_k$-$\text{Avoid}[n,n+1]$ running in time $O(n2^{\frac{k-2}{k-1}n})$, improving the naive $2^n\cdot \mathrm{poly}(n)$ bound.