Range Avoidance and Remote Point: New Algorithms and Hardness

The Range Avoidance (Avoid) problem C-Avoidn, m (n) asks that, given a circuit in a class 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 Avoid are closely related to circuit lower bounds. In particular, Korten’s work reinterpreted an earlier result from bounded arithmetic, originally proved by Jeřábek (Ann. Pure Appl. Log. 2004), as an equivalence in computational complexity between the existence of FPNP algorithms for the general Avoid problem and 2^Ω (n) lower bounds against general Boolean circuits for the class 𝐄NP. In this work, we significantly complement these works by generalizing the equivalence result to restricted circuit classes and obtain the following: - For any constant depth unbounded fan-in circuit class C ⊇ AC⁰, there is an FPNP algorithm for C-Avoidn, n^1+ε (for any constant ε > 0) if and only if 𝐄NP cannot be computed by C circuits of size 2^o (n). This addresses an open problem by Korten (Bulletin of EATCS' 25). - If 𝐄NP cannot be computed by o (2ⁿ/n) size formulas, then there is an FPNP algorithm for NC⁰-Avoidn, 2n. Note that by an extension of Ren, Santhanam, and Wang (FOCS' 22), an FPNP algorithm for NC⁰₄-Avoidn, n+n^δ for any constant δ ∈ (0, 1) implies 𝐄NP cannot be computed by o (2ⁿ/n) size formulas. These results yield the first characterizations of FPNP C-Avoid algorithms for low-complexity circuit classes such as AC⁰. We also consider the average-case analog of Avoid, the Remote Point (Remote-Point) problem, and establish: - For some suitable function c (n) and constant γ > 0, there is an FPNP algorithm for Remote-Pointn, n^6+γ, c (O⏒ (log n) ) if and only if 𝐄NP cannot be (1/2-c (n) ) -approximated by circuits of size 2^o (n). Finally, we also present two improved algorithms for NC⁰-Avoid: - A family of 2^n^{1 - ε/ (k-1) +o (1) } time algorithms for NC⁰ₖ-Avoidn, n^1+ε for any ε > 0, exhibiting the first subexponential-time algorithm for any super-linear stretch. - Faster local algorithms for NC⁰ₖ-Avoidn, n+1 running in time O (n2^ (k-2) / (k-1) n), improving the naive 2ⁿ⋅ poly (n) bound.