9 citations · 53 across the 22 of their papers we have counts for
24 papers
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…
Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More
Xin Li
A long line of work in the past two decades or so established close connections between several different pseudorandom objects and applications. These connections essentially show…
Low-Degree Polynomials Extract from Local Sources
Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman +2
We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in…
Improved Decoding of Expander Codes
Xue Chen, Kuan Cheng, Xin Li +1
We study the classical expander codes, introduced by Sipser and Spielman \cite{SS96}. Given any constants , and an arbitrary bipartite graph with verti…
Two classes of minimal generic fundamental invariants for tensors
Xin Li, Liping Zhang, Hanchen Xia
Motivated by the problems raised by Bürgisser and Ikenmeyer, we discuss two classes of minimal generic fundamental invariants for tensors of order 3. The first one is defined on $\…
Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
Jeremiah Blocki, Kuan Cheng, Elena Grigorescu +3
Locally Decodable Codes (LDCs) are error-correcting codes for which individual message symbols can be quickly recovered despite errors in the codeword. LDCs for Hamming errors have…
Efficient Linear and Affine Codes for Correcting Insertions/Deletions
Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler +1
This paper studies \emph{linear} and \emph{affine} error-correcting codes for correcting synchronization errors such as insertions and deletions. We call such codes linear/affine i…
Saxl Conjecture for triple hooks
Xin Li
We make some progresses on Saxl conjecture. Firstly, we show that the probability that a partition is comparable in dominance order to the staircase partition tends to zero as the…
Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions
Xin Li
The recent line of study on randomness extractors has been a great success, resulting in exciting new techniques, new connections, and breakthroughs to long standing open problems…
Non-Malleable Extractors and Codes for Composition of Tampering, Interleaved Tampering and More
Eshan Chattopadhyay, Xin Li
Non-malleable codes were introduced by Dziembowski, Pietrzak, and Wichs (JACM 2018) as a generalization of standard error correcting codes to handle severe forms of tampering on co…
Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets
Kuan Cheng, Bernhard Haeupler, Xin Li +2
Synchronization strings are recently introduced by Haeupler and Shahrasbi (STOC 2017) in the study of codes for correcting insertion and deletion errors (insdel codes). They showed…
Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets
Kuan Cheng, Xin Li, Ke Wu
Synchronization strings are recently introduced by Haeupler and Shahrasbi [HS17a] in the study of codes for correcting insertion and deletion errors (insdel codes). A synchronizati…
Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors
Xin Li
In this paper we give improved constructions of several central objects in the literature of randomness extraction and tamper-resilient cryptography. Our main results are: (1) An e…
Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols
Eshan Chattopadhyay, Xin Li
We make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors; 2. Constructing optimal privacy amplification protocols with an active ad…
Computing approximate PSD factorizations
Amitabh Basu, Michael Dinitz, Xin Li
We give an algorithm for computing approximate PSD factorizations of nonnegative matrices. The running time of the algorithm is polynomial in the dimensions of the input matrix, bu…
Randomness Extraction in AC0 and with Small Locality
Kuan Cheng, Xin Li
Randomness extractors, which extract high quality (almost-uniform) random bits from biased random sources, are important objects both in theory and in practice. While there have be…
Improved Constructions of Two-Source Extractors
Xin Li
In a recent breakthrough \cite{CZ15}, Chattopadhyay and Zuckerman gave an explicit two-source extractor for min-entropy for some large enough constant . Howeve…
Non-Malleable Extractors and Codes, with their Many Tampered Extensions
Eshan Chattopadhyay, Vipul Goyal, Xin Li
Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the con…
Three-Source Extractors for Polylogarithmic Min-Entropy
Xin Li
We continue the study of constructing explicit extractors for independent general weak random sources. The ultimate goal is to give a construction that matches what is given by the…
Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications
Kai-Min Chung, Xin Li, Xiaodi Wu
We study the problem of constructing multi-source extractors in the quantum setting, which extract almost uniform random bits against quantum side information collected from severa…
Non-Malleable Condensers for Arbitrary Min-Entropy, and Almost Optimal Protocols for Privacy Amplification
Xin Li
Recently, the problem of privacy amplification with an active adversary has received a lot of attention. Given a shared n-bit weak random source X with min-entropy k and a security…
Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification
Xin Li
Dodis and Wichs introduced the notion of a non-malleable extractor to study the problem of privacy amplification with an active adversary. A non-malleable extractor is a much stron…
Privacy Amplification and Non-Malleable Extractors Via Character Sums
Yevgeniy Dodis, Xin Li, Trevor D. Wooley +1
In studying how to communicate over a public channel with an active adversary, Dodis and Wichs introduced the notion of a non-malleable extractor. A non-malleable extractor dramati…
On the Problem of Local Randomness in Privacy Amplification with an Active Adversary
Xin Li
We study the problem of privacy amplification with an active adversary in the information theoretic setting. In this setting, two parties Alice and Bob start out with a shared -…