9 citations · 53 across the 22 of their papers we have counts for
4 papers · 1 filter
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…