On the Range Avoidance Problem for Circuits

We consider the range avoidance problem (called Avoid): given the description of a circuit with more output gates than input gates, find a string that is not in the range of the circuit. 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 circuitanalysis algorithms and circuit lower bounds (J. ACM 2014), we present a framework for solving $\mathscr{C}$-Avoid in FP NP using circuit-analysis data structures for $\mathscr{C}$, for “typical” multi-output circuit classes $\mathscr{C}$. As an application, we present a non-trivial FP NP range avoidance algorithm for De Morgan formulas. /inlp>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 $\mathscr{C}$-Avoid would imply breakthrough lower bounds, even for very weak circuit classes $\mathscr{C}$. In particular, an algorithm for AC 0 -Avoid with polynomial stretch implies lower bounds against NC 1, and an algorithm for $NC_{4}^{0}$-Avoid with very small stretch 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.

Authors

• Hanlin Ren
• Rahul Santhanam
• Zhikun Wang

Keywords

• Computer science
• Buildings
• Logic gates
• Probabilistic logic
• Data structures
• Generators
• Complexity theory
• Data Structure
• Lower Bound
• Probabilistic Method
• Output Gate
• Explicit Construction
• Classical Circuit
• Detailed Results
• Hardness
• Complex Circuits
• Input Length
• Total Problems
• Preprocessing Phase
• Truth Table
• Crucial Ingredient
• Rigid Matrix
• Input Bits
• Deterministic Time
• Random String
• Restricted Class
• Hamming Weight
• Output Bits
• computational complexity
• circuit complexity
• pseudorandomness