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.
