Ronen Shaltiel

Let $\cal C$ be a class of distributions over $\B^n$. A deterministic randomness extractor for $\cal C$ is a function $E:\B^n \ar \B^m$ such that for any $X$ in $\cal C$ the distribution $E(X)$ is statistically close to the uniform distribution. A long line of research deals with explicit constructions ... more >>>

Eli Ben-Sasson, Noga Ron-Zewi

Two-source and affine extractors and dispersers are fundamental objects studied in the context of derandomization. This paper shows how to construct two-source extractors and dispersers for arbitrarily small min-entropy rate in a black-box manner from affine extractors with sufficiently good parameters. Our analysis relies on the study of approximate duality, ... more >>>

Gil Cohen

This paper offers the following contributions:

* We construct a two-source extractor for quasi-logarithmic min-entropy. That is, an extractor for two independent $n$-bit sources with min-entropy $\widetilde{O}(\log{n})$. Our construction is optimal up to $\mathrm{poly}(\log\log{n})$ factors and improves upon a recent result by Ben-Aroya, Doron, and Ta-Shma (ECCC'16) that can handle ... more >>>

Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma

We show a reduction from the existence of explicit t-non-malleable

extractors with a small seed length, to the construction of explicit

two-source extractors with small error for sources with arbitrarily

small constant rate. Previously, such a reduction was known either

when one source had entropy rate above half [Raz05] or ...
more >>>

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

A code $\mathcal{C}$ is $(1-\tau,L)$ erasure list-decodable if for every codeword $w$, after erasing any $1-\tau$ fraction of the symbols of $w$,

the remaining $\tau$-fraction of its symbols have at most $L$ possible completions into codewords of $\mathcal{C}$.

Non-explicitly, there exist binary $(1-\tau,L)$ erasure list-decodable codes having rate $O(\tau)$ and ...
more >>>