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.