Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits

Hanlin Ren, Yichuan Wang, Yan Zhong

Given a circuit $G:\{0,1{\}}^n\to \{0,1{\}}^m$ with $m>n$, the *range avoidance* problem ($\text{Avoid}$) asks to output a string $y\in \{0,1{\}}^m$ that is not in the range of $G…