Given a circuit $C : \{0,1\}^n \to \{0,1\}^m$ from a circuit class $F$, with $m > n$, finding a $y \in \{0,1\}^m$ such that $\forall x \in \{0,1\}^n$, $C(x) \ne y$, is the range avoidance problem (denoted by $F$-AVOID). It is known that deterministic polynomial time algorithms (even with access to $NP$ oracles) solving this problem imply explicit constructions of various pseudorandom objects like hard Boolean functions, linear codes, PRGs etc.
Deterministic polynomial time algorithms are known for $NC^0_2$-AVOID when $m > n$, and for $NC^0_3$-AVOID when $m \ge \frac{n^2}{\log n}$, where $NC^0_k$ is the class of circuits with bounded fan-in which have constant depth and the output depends on at most $k$ of the input bits. On the other hand, it is also known that $NC^0_3$-AVOID when $m = n+O\left(n^{2/3}\right)$ is at least as hard as explicit construction of rigid matrices. In fact, algorithms for solving range avoidance for even $NC^0_4$ circuits imply new circuit lower bounds.
In this paper, we propose a new approach to solving range avoidance problem via hypergraphs. We formulate the problem in terms of Turan-type problems in hypergraphs of the following kind - for a fixed $k$-uniform hypergraph $H'$, what is the maximum number of edges that can exist in a $k$-uniform hypergraph $H$ which does not have a sub-hypergraph isomorphic to $H'$? We first demonstrate the applicability of this approach by showing alternate proofs of some of the known results for range avoidance problem using this framework.
We then use our approach to show (using several different hypergraph structures for which Turan-type bounds are known in the literature) that there is a constant $c$ such that MONOTONE-$NC^0_3$-AVOID can be solved in deterministic polynomial time when $m > cn^2$. To improve the stretch constraint to linear, we show a new Turan-type theorem for a hypergraph structure (which we call the loose $\chi$-cycles). More specifically, we prove that Any connected 3-uniform linear hypergraph with $m>n$ edges must contain a loose $\chi$ cycle. Using this, we show that MONOTONE-$NC^0_3$-AVOID can be solved in deterministic polynomial time when $m > n$, thus improving the known bounds of $NC^0_3$-AVOID for the case of monotone circuits.
In contrast, we note that efficient algorithms for solving MONOTONE-$NC^0_6$-AVOID, already imply explicit constructions for rigid matrices.
Building on this further, we show that there is a polynomial time algorithm for SYMMETRIC-$NC^0_3$-AVOID when $m > 8n$. We also generalize our argument to solve the special case of range avoidance for $NC^0_k$ where each output function computed by the circuit, is the majority function on its inputs where $m>n^2$.
