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

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$. Besides its profound connection to circuit complexity and explicit construction problems, this problem is also related to the existence of proof complexity generators – circuits $G:\{0,1{\}}^n\to \{0,1{\}}^m$ where $m>n$ but for every $y\in \{0,1{\}}^m$, it is infeasible to prove the statement “$y\in ̸\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}(G)$” in a given propositional proof system. This paper connects these two problems with the existence of demi-bits generators, a fundamental cryptographic primitive against nondeterministic adversaries introduced by Rudich (RANDOM '97). $\bullet$ We show that the existence of demi-bits generators implies $\text{Avoid}$ is hard for nondeterministic algorithms. This resolves an open problem raised by Chen and Li (STOC ‘24). Furthermore, assuming the demi-hardness of certain LPN-style generators or Goldreich’ PRG, we prove the hardness of $\text{Avoid}$ even when the instances are constant-degree polynomials over ${\mathbb{F}}_2$. $\bullet$ We show that the dual weak pigeonhole principle is unprovable in Cook’s theory ${\mathsf{P}\mathsf{V}}_1$ under the existence of demi-bits generators secure against $\mathbf{A}\mathbf{M}$, thereby separating Jerabek’s theory ${\mathsf{A}\mathsf{P}\mathsf{C}}_1$ from ${\mathsf{P}\mathsf{V}}_1$. $\bullet$ We transform demi-bits generators to proof complexity generators that are pseudo-surjective with nearly optimal parameters. Our constructions build on the recent breakthroughs on the hardness of $\text{Avoid}$ by Ilango, Li, and Williams (STOC '23) and Chen and Li (STOC '24). We use randomness extractors to significantly simplify the construction and the proof.