Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources

In this work we show how to deterministically extract high quality randomness from several independent sources of low quality randomness.

We construct an extractor that can extract from a constant (c) number of independent sources of length n (N = 2n), each of which have min-entropy that is polynomially small in n (say ndelta for some arbitrarily small constant delta). Our extractor is built by composing previous constructions of strong seeded extractors in simple ways. We introduce a new technique to condense somewhere random sources that seems like a useful way to manipulate independent sources.

Speaker Details

Anup Rao is graduated from UT Austin and postdoc’ed at the Center for Computational Intractibility and the Institute for Advanced Study before becoming a professor at UW.

Date:
Speakers:
Anup Rao
Affiliation:
University of Texas at Austin

    • Portrait of Jeff Running

      Jeff Running