💻 computer science

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

This paper establishes that the existence of demi-bit generators implies the hardness of the Range Avoidance problem for nondeterministic algorithms and the unprovability of the dual weak pigeonhole principle in Cook's theory $\mathsf{PV}_1$ , while also providing simplified constructions of pseudo-surjective proof complexity generators with nearly optimal parameters.

Original authors: Hanlin Ren, Yichuan Wang, Yan Zhong

Published 2026-03-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hanlin Ren, Yichuan Wang, Yan Zhong

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Impossible" Puzzle

Imagine you have a machine (a circuit) that takes a small key (say, 100 bits) and turns it into a much larger code (say, 1,000 bits). Because the machine has a small key but makes a huge code, it can't possibly make every possible 1,000-bit code. There are trillions of codes it simply cannot produce.

The Problem (Range Avoidance):
Your job is to find one code that this machine cannot make.

The Easy Way: If you are allowed to guess randomly, you will almost certainly find a code the machine didn't make. It's like throwing a dart at a wall; the machine only painted a tiny dot on the wall, so you'll almost certainly hit the blank space.
The Hard Way: If you have to be deterministic (no guessing, just pure logic) or nondeterministic (trying every possibility at once, like a super-fast parallel computer), finding that blank spot becomes incredibly difficult.

This paper asks: Is it actually impossible for these smart computers to find the blank spot?

The authors say: Yes, it is impossible, provided that a specific type of "magic trick" (called a Demi-Bit) exists in the world of cryptography.

Key Concept 1: The "Demi-Bit" (The Magic Trick)

To understand the paper, you need to understand the Demi-Bit Generator.

Normal Pseudorandom Generator: Imagine a magician who shuffles a deck of cards. If you look at the top card, it looks random. But if you have a super-smart detective (a computer), they might eventually figure out the trick and predict the next card.
Demi-Bit Generator: This is a super-magician. Even if the detective is allowed to use "magic" (nondeterminism—trying all possibilities at once), they still cannot predict the next card. The card looks completely random to the detective, even though it was generated by a simple rule.

The Paper's Discovery:
The authors proved that if this "super-magician" (Demi-Bit) exists, then the "Impossible Puzzle" (Range Avoidance) is truly unsolvable for smart computers. If you could solve the puzzle, you could expose the magician's trick, proving the Demi-Bit wasn't magic at all.

Key Concept 2: The "Proof Complexity" (The Courtroom)

The paper also talks about Proof Complexity. Imagine a courtroom where a lawyer (the Proof System) tries to prove a statement is true.

The Statement: "This specific code $y$ was not made by the machine."
The Goal: The lawyer needs to write a proof so short and convincing that the judge accepts it quickly.

Usually, if a code wasn't made by the machine, it's easy to prove. But the authors show that if the Demi-Bit exists, there are codes where the lawyer cannot write a short proof. No matter how hard they try, the proof would have to be millions of pages long.

The Analogy:
Imagine a lock that is so complex that even if you know the key doesn't fit, you can't write down a simple sentence explaining why it doesn't fit. You'd need a book to explain it. The paper shows that these "unexplainable" locks exist if the Demi-Bit exists.

Key Concept 3: The "Student and Teacher" Game

The paper uses a game to explain why this matters for math logic.

The Game: A Student (a computer trying to solve the puzzle) asks a Teacher (who knows everything) for help.
- The Student guesses a code.
- If the code was made by the machine, the Teacher says, "No, here is the key that made it."
- The Student uses that key to make a better guess.
- They play for $k$ rounds.
The Result: The paper proves that if the Demi-Bit exists, the Student cannot win the game, no matter how many rounds they play (as long as the rounds are limited). The Teacher always has a counter-move.

Why does this matter?
This connects to Bounded Arithmetic (a branch of math logic).

PV1: A logical system that represents "standard" computer reasoning.
APC1: A stronger system that includes "randomized" reasoning.
The Breakthrough: The authors proved that APC1 is strictly stronger than PV1. In plain English: There are things you can prove if you are allowed to use randomness, that you cannot prove if you are forced to be purely deterministic. This settles a decades-old question in math logic.

The Three Big Wins of the Paper

Simpler Assumptions: Previous papers required "super-magic" (like Indistinguishability Obfuscation) to prove these things. This paper says, "We don't need that heavy magic. We just need the lighter, more basic 'Demi-Bit' magic." This makes the result more believable and grounded.
Simpler Circuits: They showed that even if the machine is very simple (made of basic math operations like XOR and AND), the puzzle is still hard. It's not just hard for complex machines; it's hard for simple ones too.
The "Best-Case" Surprise: Usually, in computer science, we worry about the "worst-case" scenario (the hardest input). But in this paper, they show that even the best possible input (the easiest code to find) is still hard to prove. It's like saying, "Even the easiest puzzle in the world is impossible to solve if you follow these rules."

Summary in One Sentence

If a specific type of cryptographic "magic trick" (Demi-Bit) exists, then computers cannot find the "holes" in random number generators, cannot write short proofs for why those holes exist, and cannot win a guessing game against an all-knowing teacher, proving that some logical truths are fundamentally beyond the reach of standard deterministic reasoning.

1. Problem Statement

The paper addresses two interconnected problems in theoretical computer science:

Range Avoidance (Avoid): Given a Boolean circuit $G: \{0,1\}^n \to \{0,1\}^m$ with $m > n$ , the goal is to find a string $y \in \{0,1\}^m$ such that $y \notin \text{Range}(G)$ . While a trivial randomized algorithm exists (output a random string), the existence of efficient deterministic or nondeterministic algorithms is a major open problem. Solving Avoid deterministically implies breakthroughs in explicit constructions and circuit lower bounds.
Proof Complexity Generators: A circuit $G$ is a proof complexity generator against a proof system $P$ if the statement " $y \notin \text{Range}(G)$ " requires super-polynomial proofs in $P$ for every $y$ . This connects computational hardness to the unprovability of statements in formal systems.

The authors aim to establish the hardness of Avoid and the existence of proof complexity generators under weaker cryptographic assumptions than previously known, specifically moving from "Cryptomania" (e.g., Indistinguishability Obfuscation) to "Minicrypt" (e.g., One-Way Functions/Pseudorandom Generators) settings, but against nondeterministic adversaries.

2. Core Methodology

The central innovation of the paper is the use of Demi-Bits Generators, a primitive introduced by Rudich (1997).

Demi-Bits: A function $G: \{0,1\}^n \to \{0,1\}^m$ is a demi-bits generator if no nondeterministic adversary (specifically in $\text{NP/poly}$ or $\text{AM}$ ) can distinguish the output of $G$ from a truly random string with non-negligible advantage, even though the adversary can verify membership in the range.
Extraction Technique: The authors employ randomness extractors (specifically pairwise independent hash functions) to transform a demi-bits generator into a hard instance for Range Avoidance.
- They construct a new circuit $C_r(s) = \text{Ext}(G(s), r)$ , where $\text{Ext}$ is a strong seeded extractor and $r$ is a random seed.
- They prove that if a nondeterministic algorithm could solve Avoid for $C_r$ , it could be used to construct a nondeterministic adversary that breaks the security of the underlying demi-bits generator $G$ .
Student-Teacher Games: To prove results in bounded arithmetic and proof complexity, the authors utilize the Student-Teacher game framework. A "Student" (algorithm) tries to find a string outside the range of $G$ by querying a "Teacher" (who provides preimages for failed queries). The hardness of this game corresponds to the unprovability of the range avoidance statement in bounded arithmetic theories.

3. Key Contributions and Results

A. Hardness of Range Avoidance (Avoid)

Main Theorem (Theorem 1.1): The existence of demi-bits generators with sufficient stretch (e.g., $G: \{0,1\}^n \to \{0,1\}^{10n}$ $G : {0, 1}^{n} \to {0, 1}^{10 n}$ ) implies that Avoid $\notin$ SearchNP.
- Significance: This resolves an open problem by Chen and Li (STOC '24). It shows that Avoid is hard for nondeterministic algorithms under "Minicrypt-style" assumptions (demi-bits) rather than the stronger "Cryptomania" assumptions (iO, LWE) used in prior work.
- Simplification: The proof is significantly simpler (fitting in half a page) compared to previous works, relying on elementary pseudorandom constructions and the Leftover Hash Lemma.
Restricted Circuits (Corollary 1.3): Assuming demi-bits generators computable by constant-degree polynomials over $\mathbb{F}_2$ (e.g., based on LPN or Goldreich's PRG), the Range Avoidance problem remains hard for XOR $\circ$ AND $_d$ circuits (constant-degree polynomials). This extends hardness results to restricted circuit classes previously unknown.

B. Proof Complexity Generators

Transformation (Theorem 1.4): The authors show that demi-bits generators secure against a proof system $P$ $P$ can be transformed into proof complexity generators secure against $P$ $P$ , provided $P$ $P$ is closed under "simple parity reductions."
- This provides a new, modular approach to constructing proof complexity generators: one only needs to construct a demi-bits generator against the specific proof system.
Pseudo-Surjectivity (Theorem 1.7): Under the assumption of demi-bits generators secure against $\text{NP/poly}$ $NP/poly$ , the authors construct generators that are $k$ -round pseudo-surjective.
- Pseudo-surjectivity is the strongest known hardness notion for proof complexity generators, implying that even interactive protocols (Student-Teacher games) cannot efficiently find a string outside the range.
- Limitation: The parameters do not yet reach the regime required to prove the pseudo-surjectivity of the Truth Table Generator (which would imply circuit lower bounds are unprovable in $P$ ), but this is shown to be an inherent limitation of the current generality.

C. Separation of Bounded Arithmetic Theories

Separating $\text{PV}_1$ and $\text{APC}_1$ (Theorem 1.5): The paper proves that the Dual Weak Pigeonhole Principle (dwPHP) for polynomial-time functions is unprovable in Cook's theory $\text{PV}_1$ $PV_{1}$ (deterministic polynomial time reasoning), assuming the existence of demi-bits generators secure against $\text{AM/O(1)}$ $AM/O(1)$ .
- This implies that Jeřábek's theory $\text{APC}_1$ (which includes dwPHP) is a strict extension of $\text{PV}_1$ .
- Previous separations relied on iO or unlikely assumptions; this result uses a more natural cryptographic primitive against nondeterministic adversaries.
Round Complexity (Theorem 1.6): The authors generalize this to rule out deterministic polynomial-time Students winning the Student-Teacher game in $k$ rounds, assuming demi-bits secure against $\text{AM/O(\log k)}$ .

4. Significance and Impact

Weakening Assumptions: The paper successfully shifts the hardness of Range Avoidance from "Cryptomania" (iO, subexponential LWE) to "Minicrypt" (demi-bits, potentially based on LPN/PRGs). This is a crucial step toward basing complexity separations on minimal cryptographic assumptions.
Conceptual Clarity: By isolating the core mechanism (demi-bits + extraction), the authors provide a cleaner, more modular framework for proving hardness. This simplifies the proofs of previous results and opens the door to generalizations.
Average-Case to Best-Case Reduction: The paper highlights a unique phenomenon in proof complexity: transforming an average-case hardness assumption (demi-bits are hard to distinguish on average) into a best-case hardness result (proof complexity generators are hard for every output $y$ ). This "average-case to best-case" reduction is unique to the setting of nondeterministic adversaries and proof complexity.
New Directions for Lower Bounds: The results suggest a concrete path to proving lower bounds for strong proof systems (like $\text{Res}[\oplus]$ ): first construct a demi-bits generator against that system, then apply the transformation theorem.

5. Conclusion

Ren, Wang, and Zhong establish a fundamental link between demi-bits generators and the hardness of Range Avoidance and Proof Complexity. Their work demonstrates that the existence of these cryptographic primitives against nondeterministic adversaries is sufficient to separate major complexity classes (SearchNP vs. Avoid), separate bounded arithmetic theories ( $\text{PV}_1$ vs. $\text{APC}_1$ ), and construct strong proof complexity generators. The results represent a significant simplification and strengthening of the theoretical foundations connecting cryptography, circuit complexity, and proof complexity.