Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR25-049 | 25th April 2025 17:37

Range Avoidance and Remote Point for Low-Depth Circuits: New Algorithms and Hardness

RSS-Feed




Revision #1
Authors: Xin Li, Yan Zhong
Accepted on: 25th April 2025 17:37
Downloads: 16
Keywords: 


Abstract:

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.



Changes to previous version:

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.


Paper:

TR25-049 | 13th April 2025 08:01

Range Avoidance and Remote Point for Low-Depth Circuits: New Algorithms and Hardness





TR25-049
Authors: Xin Li, Yan Zhong
Publication: 13th April 2025 14:29
Downloads: 241
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint