Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with two-source extractors:
TR05-145 | 5th December 2005
Ronen Shaltiel

How to get more mileage from randomness extractors

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 >>>

TR10-144 | 20th September 2010
Eli Ben-Sasson, Noga Ron-Zewi

From Affine to Two-Source Extractors via Approximate Duality

Revisions: 1

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 >>>

TR16-114 | 30th July 2016
Gil Cohen

Two-Source Extractors for Quasi-Logarithmic Min-Entropy and Improved Privacy Amplification Protocols

Revisions: 1

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 >>>

TR17-027 | 16th February 2017
Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma

A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate

Revisions: 1

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 >>>

TR18-065 | 8th April 2018
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends

Revisions: 1

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 >>>

ISSN 1433-8092 | Imprint