3 papers
cs.CC2026
Exponential Sampling Lower Bounds for Polynomial Sources
Yan Zhong
A degree- polynomial source is the output of a polynomial map of degree at most over on arbitrarily many uniform random bits. Khodabandeh and Shinkar (FOCS '2…
cs.CC2025
Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
Hanlin Ren, Yichuan Wang, Yan Zhong
Given a circuit with , the *range avoidance* problem () asks to output a string that is not in the range of $G…
cs.CC2024
Two-Source and Affine Non-Malleable Extractors for Small Entropy
Xin Li, Yan Zhong
Non-malleable extractors are generalizations and strengthening of standard randomness extractors, that are resilient to adversarial tampering. Such extractors have wide application…