Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > YICHUAN WANG:
All reports by Author Yichuan Wang:

TR25-191 | 18th November 2025
Hanlin Ren, Yichuan Wang, Yan Zhong

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 ... more >>>




ISSN 1433-8092 | Imprint