Welcome to the resource topic for 2025/2114
Title:
Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
Authors: Hanlin Ren, Yichuan Wang, Yan Zhong
Abstract: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\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’s 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}/_{O(1)}, thereby separating Jeřábek’s theory \mathsf{APC}_1 from \mathsf{PV}_1. Previously, Ilango, Li, and Williams (STOC '23) obtained the same separation under different (and arguably stronger) cryptographic assumptions.
\bullet We transform demi-bits generators to proof complexity generators that are pseudo-surjective in certain parameter regime. Pseudo-surjectivity is the strongest form of hardness considered in the literature for proof complexity generators.
Our constructions are inspired by 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.
ePrint: https://eprint.iacr.org/2025/2114
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .