Yichuan Wang

collaborators

2 papers

cs.CC2025

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

Hanlin Ren, Yichuan Wang, Yan Zhong

Given a circuit $G : {0, 1}^{n} \to {0, 1}^{m}$ with $m > n$ , the *range avoidance* problem ( $Avoid$ ) asks to output a string $y \in {0, 1}^{m}$ that is not in the range of $G…

cs.DS2024

Tight Streaming Lower Bounds for Deterministic Approximate Counting

Yichuan Wang

We study the streaming complexity of $k$ -counter approximate counting. In the $k$ -counter approximate counting problem, we are given an input string in $[k]^{n}$ , and we are required…