Ball, Marshall ;
Goldreich, Oded ;
Malkin, Tal
Randomness Extraction from Somewhat Dependent Sources
Abstract
We initiate a comprehensive study of the question of randomness extractions from two somewhat dependent sources of defective randomness. Specifically, we present three natural models, which are based on different natural perspectives on the notion of bounded dependency between a pair of distributions. Going from the more restricted model to the less restricted one, our models and main results are as follows.
1) Bounded dependence as bounded coordination: Here we consider pairs of distributions that arise from independent random processes that are applied to the outcome of a single global random source, which may be viewed as a mechanism of coordination (which is adversarial from our perspective).
We show that if the minentropy of each of the two outcomes is larger than the length of the global source, then extraction is possible (and is, in fact, feasible). We stress that the extractor has no access to the global random source nor to the internal randomness that the two processes use, but rather gets only the two dependent outcomes.
This model is equivalent to a setting in which the two outcomes are generated by two independent sources, but then each outcome is modified based on limited leakage (equiv., communication) between the two sources.
(Here this leakage is measured in terms of the number of bits that were communicated, but in the next model we consider the actual influence of this leakage.)
2) Bounded dependence as bounded cross influence: Here we consider pairs of outcomes that are produced by a pair of sources such that each source has bounded (worstcase) influence on the outcome of the other source. We stress that the extractor has no access to the randomness that the two processes use, but rather gets only the two dependent outcomes.
We show that, while (proper) randomness extraction is impossible in this case, randomness condensing is possible and feasible; specifically, the randomness deficiency of condensing is linear in our measure of cross influence, and this upper bound is tight. We also discuss various applications of such condensers, including for cryptography, standard randomized algorithms, and sublineartime algorithms, while pointing out their benefit over using a seeded (singlesource) extractor.
3) Bounded dependence as bounded mutual information: Due to the averagecase nature of mutual information, here there is a tradeoff between the error (or deviation) probability of the extracted output and its randomness deficiency. Loosely speaking, for joint distributions of mutual information t, we can condense with randomness deficiency O(t/ε) and error ε, and this tradeoff is optimal. All positive results are obtained by using a standard twosource extractor (or condenser) as a blackbox.
BibTeX  Entry
@InProceedings{ball_et_al:LIPIcs.ITCS.2022.12,
author = {Ball, Marshall and Goldreich, Oded and Malkin, Tal},
title = {{Randomness Extraction from Somewhat Dependent Sources}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {12:112:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15608},
URN = {urn:nbn:de:0030drops156081},
doi = {10.4230/LIPIcs.ITCS.2022.12},
annote = {Keywords: Randomness Extraction, minentropy, mutual information, twosource extractors, twosource condenser}
}
25.01.2022
Keywords: 

Randomness Extraction, minentropy, mutual information, twosource extractors, twosource condenser 
Seminar: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Issue date: 

2022 
Date of publication: 

25.01.2022 