Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms

Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje +1

Range Avoidance (AVOID) is a total search problem where, given a Boolean circuit $C:\{0,1{\}}^n\to \{0,1{\}}^m$, $m>n$, the task is to find a $y\in \{0,1{\}}^m$ outside the range of $…