For a propositional proof system $\mathcal{P}$ and a polynomial-time function $G: \{0, 1\}^n \to \{0, 1\}^N$ ($N > 10n$), we say that $G$ is a *proof complexity generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the (suitably encoded) statement "$y\not\in\mathrm{Range}(G)$" for every $y \in \{0, 1\}^N$, and $G$ is a *demi-bits generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the statement "$y \not\in\mathrm{Range}(G)$" for a noticeable fraction of $y \in \{0, 1\}^N$. As can be seen from the definitions, proof complexity generators are qualitatively stronger objects than demi-bits generators.
Our main result is that, perhaps counter-intuitively, every demi-bits generator "contains" exponentially many proof complexity generators. In fact, a random subset of output bits of a demi-bits generator forms a proof complexity generator with constant probability. This result is an extremely simple corollary of Pajor's Lemma (a strengthening of the well-known Sauer--Shelah Lemma).
This result allows us to exhibit the hardness of the Range Avoidance problem ($\text{Avoid}$) in several new, restricted settings of interest:
* We show that demi-bits generators computable in $\text{NC}^0$ implies the hardness of $\text{NC}^0$-$\text{Avoid}$ up to constant factors in the stretch, demonstrating a barrier to further improvements on the recent progress on this problem (Korten--Pitassi--Impagliazzo, FOCS'25; Guruswami--Lyu--Yuan, SODA'26).
* Given a linear space $V\subseteq \mathrm{GF}(2)^n$ of dimension $k$, the $\text{XOR}$-$\text{Remote-Point}$ problem asks to find a vector far from $V$ (Alon--Panigrahy--Yekhanin, RANDOM'09). Assuming a demi-hardness version of LPN (Learning Parity with Noise), we show that $\text{XOR}$-$\text{Remote-Point}$ cannot be solved by efficient nondeterministic algorithms.
* An intriguing challenge in circuit complexity is to build a partial Boolean function on a given domain that has high circuit complexity (Arvind--Srinivasan, ICS'10; Chen--Huang--Li--Ren, STOC'23). Even for hardness against *polynomial-size DNFs*, no efficient algorithm is known for this task. We show that under a version of the random $k$-SAT Hypothesis against $\text{AM}$ algorithms, such hard functions cannot be constructed in nondeterministic polynomial time.
Along the way, we introduce the notion of *zero-error disperser families* that can transform demi-bits generators into proof complexity generators, and show that this family can be computed by projections (i.e., without any circuit complexity overhead). Using a different instantiation of this family, we construct proof complexity generators from *barely non-trivial* demi-bits generators $G: \{0, 1\}^n \to \{0, 1\}^N$, where the number of hard-to-prove statements of the form "$y \not \in \mathrm{Range}(G)$" just slightly exceeds $2^n$ (which is the number of *false* statements of this form).
