Abstract
The range avoidance problem, denoted as C-Avoid, asks to find a non-output of a given C-circuit C: {0, 1}^n -> {0, 1}^L with stretch L > n. This problem has recently received much attention in complexity theory for its connections with circuit lower bounds and other explicit construction problems. Inspired by the Algorithmic Method for circuit lower bounds, Ren, Santhanam, and Wang (FOCS'22) established a framework to design FP^NP algorithms for C-Avoid via slightly non-trivial data structures related to C. However, a major drawback of their approach is the lack of unconditional results even for C = AC^0.
In this work, we present the first unconditional FP^NP algorithm for ACC^0-Avoid. Indeed, we obtain FP^NP algorithms for the following stronger problems:
* (ACC^0-Remote-Point). Given an ACC^0 circuit C: {0, 1}^n -> {0, 1}^L for L = quasi-poly(n), we can find some y \in {0, 1}^L in FP^NP such that for every x \in {0, 1}^n, the relative Hamming distance between y and C(x) is at least 1/2 - 1/poly(n). This problem is the "average-case" analogue of ACC^0-Avoid.
* (ACC^0-Partial-AvgHard). Given m = quasi-poly(n) inputs x_1, ..., x_m \in {0, 1}^n, we can compute m bits y_1, ..., y_m \in {0, 1} in FP^NP such that for every small ACC^0 circuit C, Pr_i[C(x_i) != y_i] >= 1/2 - 1/poly(n). This problem generalises the strong average-case circuit lower bounds against ACC^0 in a different way.
Both problems above have been studied prior to our work and no FP^NP algorithm was known even for weak circuit classes such GF(2)-linear circuits and DNF formulas. Also, both algorithms above imply, as simple corollaries, the best known lower bounds against ACC^0 circuits by Chen, Lyu, and Williams (FOCS'20).
Our results follow from a strengthened algorithmic method: slightly non-trivial algorithms for the Satisfying-Pairs problem for C implies FP^NP algorithms for C-Avoid (as well as C-Remote-Point and C-Partial-AvgHard). Here, given C-circuits {C_i} and inputs {x_j}, the C-Satisfying-Pairs problem asks to (approximately) count the number of pairs (i, j) such that C_i(x_j) = 1.
A main technical ingredient that allows us to generalise the framework for Avoid to the average-case scenarios is a new construction of a short, smooth, and rectangular PCP of Proximity, which may be of independent interest.