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 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.