{"ID":2839791,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.14061","arxiv_id":"2511.14061","title":"Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits","abstract":"Given a circuit $G: \\{0, 1\\}^n \\to \\{0, 1\\}^m$ with $m \u003e 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 \u003e n$ but for every $y\\in \\{0, 1\\}^m$, it is infeasible to prove the statement \"$y\\not\\in\\mathrm{Range}(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{PV}_1$ under the existence of demi-bits generators secure against $\\mathbf{AM}$, thereby separating Jerabek's theory $\\mathsf{APC}_1$ from $\\mathsf{PV}_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.","short_abstract":"Given a circuit $G: \\{0, 1\\}^n \\to \\{0, 1\\}^m$ with $m \u003e 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 o...","url_abs":"https://arxiv.org/abs/2511.14061","url_pdf":"https://arxiv.org/pdf/2511.14061v2","authors":"[\"Hanlin Ren\",\"Yichuan Wang\",\"Yan Zhong\"]","published":"2025-11-18T02:40:39Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.CR\"]","methods":"[]","has_code":false}