Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms

The range avoidance problem, denoted as C -Avoid, asks to find a non-output of a given C -circuit 𝐶 : 0, 1 𝑛 → 0, 1 ℓ with stretch ℓ > 𝑛. 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 𝐶 : 0, 1 𝑛 → 0, 1 ℓ for some ℓ = quasi-poly(𝑛) such that each output bit of 𝐶 is computed by a quasi-poly(𝑛)-size AC 0 [𝑚] circuit, we can find some 𝑦 ∈ 0, 1 ℓ in FP NP such that for every 𝑥 ∈ 0, 1 𝑛 , the relative Hamming distance between 𝑦 and 𝐶 (𝑥) is at least 1/2 -1/poly(𝑛). This problem is the "average-case" analogue of ACC 0 -Avoid. ), where 𝑐 = 𝑂 (1). This problem generalises the strong average-case circuit lower bounds against ACC 0 in a different way.

Our algorithms can be seen as natural generalisations of the best known almost-everywhere average-case lower bounds against ACC 0 circuits by Chen, Lyu, and Williams (FOCS'20). Note that both problems above have been studied prior to our work, and no FP NP algorithm was known even for weak circuit classes such as GF(2)-linear circuits and DNF formulas.