All reports by Author Xin Li:

__
TR23-058
| 23rd April 2023
__

Xin Li, Yan Zhong#### Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs

__
TR22-082
| 27th May 2022
__

Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João Ribeiro#### Low-Degree Polynomials Extract from Local Sources

__
TR20-060
| 23rd April 2020
__

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li#### Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols

__
TR19-184
| 13th December 2019
__

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li#### Extractors for Adversarial Sources via Extremal Hypergraphs

__
TR18-082
| 21st April 2018
__

Xin Li, Shachar Lovett, Jiapeng Zhang#### Sunflowers and Quasi-sunflowers from Randomness Extractors

__
TR15-075
| 29th April 2015
__

Eshan Chattopadhyay, Vipul Goyal, Xin Li#### Non-Malleable Extractors and Codes, with their Many Tampered Extensions

Revisions: 1

__
TR14-149
| 10th November 2014
__

Kai-Min Chung, Xin Li, Xiaodi Wu#### Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications

Xin Li, Yan Zhong

Affine extractors give some of the best-known lower bounds for various computational models, such as AC$^0$ circuits, parity decision trees, and general Boolean circuits. However, they are not known to give strong lower bounds for read-once branching programs (ROBPs). In a recent work, Gryaznov, Pudl\'{a}k, and Talebanfard (CCC' 22) introduced ... more >>>

Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João Ribeiro

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 the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, ... more >>>

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li

In a recent work, Kumar, Meka, and Sahai (FOCS 2019) introduced the notion of bounded collusion protocols (BCPs), in which $N$ parties wish to compute some joint function $f:(\{0,1\}^n)^N\to\{0,1\}$ using a public blackboard, but such that only $p$ parties may collude at a time. This generalizes well studied models in ... more >>>

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li

Randomness extraction is a fundamental problem that has been studied for over three decades. A well-studied setting assumes that one has access to multiple independent weak random sources, each with some entropy. However, this assumption is often unrealistic in practice. In real life, natural sources of randomness can produce samples ... more >>>

Xin Li, Shachar Lovett, Jiapeng Zhang

The Erdos-Rado sunflower theorem (Journal of Lond. Math. Soc. 1960) is a fundamental result in combinatorics, and the corresponding sunflower conjecture is a central open problem. Motivated by applications in complexity theory, Rossman (FOCS 2010) extended the result to quasi-sunflowers, where similar conjectures emerge about the optimal parameters for which ... more >>>

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 context and study of tamper resilient cryptography. These are \emph{seeded non-malleable extractors}, introduced by Dodis and Wichs \cite{DW09}; \emph{seedless non-malleable extractors}, introduced by Cheraghchi and Guruswami ... more >>>

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 several initially independent classical random sources. This is a natural generalization of seeded randomness extraction against quantum side information and classical independent source extraction. With new ... more >>>