On the Range Avoidance Problem for Circuits

We consider the range avoidance problem (called Avoid): given the description of a circuit C : 0, 1 n → 0, 1 ℓ (where ℓ > n), find a string y ∈ 0, 1 ℓ that is not in the range of C. This problem is complete for the class APEPP that corresponds to explicit constructions of objects whose existence follows from the probabilistic method (Korten, FOCS 2021).

Motivated by applications in explicit constructions and complexity theory, we initiate the study of the range avoidance problem for weak circuit classes, and obtain the following results:

1. Generalising Williams's connections between circuit-analysis algorithms and circuit lower bounds (J. ACM 2014), we present a framework for solving C -Avoid in FP NP using circuitanalysis data structures for C , for "typical" multi-output circuit classes C . As an application, we present a non-trivial FP NP range avoidance algorithm for De Morgan formulas.

An important technical ingredient is a construction of rectangular PCPs of proximity, building on the rectangular PCPs by Bhangale, Harsha, Paradise, and Tal (FOCS 2020).

2. Using the above framework, we show that circuit lower bounds for E NP are equivalent to circuit-analysis algorithms with E NP preprocessing. This is the first equivalence result regarding circuit lower bounds for E NP . Our equivalences have the additional advantages that they work in both infinitely-often and almost-everywhere settings, and that they also hold for larger (e.g., subexponential) size bounds.

3. Complementing the above results, we show that in some settings, solving C -Avoid would imply breakthrough lower bounds, even for very weak circuit classes C . In particular, an algorithm for AC 0 -Avoid with polynomial stretch (i.e., ℓ = poly(n)) implies lower bounds against NC 1 , and an algorithm for NC 0 4 -Avoid with very small stretch (i.e., ℓ = n + n o( 1) ) implies lower bounds against NC 1 and branching programs. 4. We show that Avoid is in FNP if and only if there is a propositional proof system that breaks every non-uniform proof complexity generator. This result connects the study of range avoidance with fundamental questions in proof complexity.