Range Avoidance in Boolean Circuits via Turan-type Bounds

Neha Kuntewar, Jayalal Sarma

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 av…