Showing cs.CCShow all
4 papers · 1 filter
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…
cs.CC2023
Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
Xin Li, Yan Zhong
In a recent work, Gryaznov, Pudlák, and Talebanfard (CCC' 22) introduced a stronger version of affine extractors known as directional affine extractors, together with a generalizat…