Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > INDEPENDENT:
Reports tagged with independent:
TR10-190 | 9th December 2010
Xin Li

#### Improved Constructions of Three Source Extractors

We study the problem of constructing extractors for independent weak random sources. The probabilistic method shows that there exists an extractor for two independent weak random sources on $n$ bits with only logarithmic min-entropy. However, previously the best known explicit two source extractor only achieves min-entropy $0.499n$ \cite{Bourgain05}, and the ... more >>>

TR12-147 | 7th November 2012
Xin Li

#### New Independent Source Extractors with Exponential Improvement

We study the problem of constructing explicit extractors for independent general weak random sources. For weak sources on $n$ bits with min-entropy $k$, perviously the best known extractor needs to use at least $\frac{\log n}{\log k}$ independent sources \cite{Rao06, BarakRSW06}. In this paper we give a new extractor that only ... more >>>

TR13-025 | 6th February 2013
Xin Li

#### Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy

Revisions: 1

We study the problem of constructing explicit extractors for independent general weak random sources. Given weak sources on $n$ bits, the probabilistic method shows that there exists a deterministic extractor for two independent sources with min-entropy as small as $\log n+O(1)$. However, even to extract from a constant number of ... more >>>

TR18-028 | 7th February 2018
Xin Li

#### Pseudorandom Correlation Breakers, Independence Preserving Mergers and their Applications

Revisions: 1

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 in the following five seemingly different topics: seeded non-malleable extractors, privacy amplification protocols with an active adversary, independent source extractors (and explicit Ramsey ... more >>>

ISSN 1433-8092 | Imprint