2 citations · 2 across the 6 of their papers we have counts for
8 papers
Non-Malleable Affine Extractors with Small Error and Complexity Lower Bounds
Xin Li, Yan Zhong
We construct explicit non-malleable affine extractors for every constant entropy rate, with linear output length and exponentially small error, against any fixed number of affine t…
Many Proof Complexity Generators Inside One Demi-Bits Generator
Xin Li, Hanlin Ren, Yan Zhong
For a propositional proof system and a polynomial-time function (), we say that is a *proof complexity generator* against…
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…
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…
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…
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…
Quantum networks with coherent routing of information through multiple nodes
Hlér Kristjánsson, Yan Zhong, Anthony Munson +1
Large-scale communication networks, such as the internet, rely on routing packets of data through multiple intermediate nodes to transmit information from a sender to a receiver. I…
Improved Online Correlated Selection
Ruiquan Gao, Zhongtian He, Zhiyi Huang +3
This paper studies the online correlated selection (OCS) problem. It was introduced by Fahrbach, Huang, Tao, and Zadimoghaddam (2020) to obtain the first edge-weighted online bipar…