Document Open Access Logo

Randomness Extraction from Somewhat Dependent Sources

Authors Marshall Ball , Oded Goldreich , Tal Malkin

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.12.pdf
  • Filesize: 0.69 MB
  • 14 pages

Document Identifiers

Author Details

Marshall Ball
  • Computer Science Department, Columbia University, New York, NY, USA
Oded Goldreich
  • Faculty of Mathematics and Computer Science, Weizmann Institute of Science, Rehovot, Israel
Tal Malkin
  • Computer Science Department, Columbia University, New York, NY, USA

Funding

This work was supported in part by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA) via Contract No. 2019-1902070006. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either express or implied, of ODNI, IARPA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein.
  • Ball, Marshall: Partially supported by an IBM Research PhD Fellowship.
  • Goldreich, Oded: Partially supported by an ISF grant number (Nr. 1146/18) and received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 819702); research was conducted while he enjoyed the hospitality of the computer science department at Columbia University.

Cite As Get BibTex

Marshall Ball, Oded Goldreich, and Tal Malkin. Randomness Extraction from Somewhat Dependent Sources. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.12

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 min-entropy 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 (worst-case) 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 sublinear-time algorithms, while pointing out their benefit over using a seeded (single-source) extractor. 
3) Bounded dependence as bounded mutual information: Due to the average-case nature of mutual information, here there is a trade-off 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 trade-off is optimal.  All positive results are obtained by using a standard two-source extractor (or condenser) as a black-box.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • Randomness Extraction
  • min-entropy
  • mutual information
  • two-source extractors
  • two-source condenser

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Divesh Aggarwal, Maciej Obremski, João L. Ribeiro, Luisa Siniscalchi, and Ivan Visconti. How to extract useful randomness from unreliable sources. In EUROCRYPT (1), volume 12105 of Lecture Notes in Computer Science, pages 343-372. Springer, 2020. Google Scholar
  2. Marshall Ball, Oded Goldreich, and Tal Malkin. Randomness extraction from somewhat dependent sources. Electron. Colloquium Comput. Complex., page 183, 2019. Google Scholar
  3. Avraham Ben-Aroya, Gil Cohen, Dean Doron, and Amnon Ta-Shma. Two-source condensers with low error and small entropy gap via entropy-resilient functions. In APPROX-RANDOM, volume 145 of LIPIcs, pages 43:1-43:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  4. Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, and Xin Li. Extractors for adversarial sources via extremal hypergraphs. In STOC, pages 1184-1197. ACM, 2020. Google Scholar
  5. Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. Electron. Colloquium Comput. Complex., page 119, 2015. Google Scholar
  6. Benny Chor and Oded Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput., 17(2):230-261, 1988. Google Scholar
  7. Yevgeniy Dodis, Thomas Ristenpart, and Salil P. Vadhan. Randomness condensers for efficiently samplable, seed-dependent sources. In TCC, volume 7194 of Lecture Notes in Computer Science, pages 618-635. Springer, 2012. Google Scholar
  8. Eran Gat and Shafi Goldwasser. Probabilistic search algorithms with unique answers and their cryptographic applications. Electron. Colloquium Comput. Complex., page 136, 2011. Google Scholar
  9. Oded Goldreich. Another motivation for reducing the randomness complexity of algorithms. In Studies in Complexity and Cryptography, volume 6650 of Lecture Notes in Computer Science, pages 555-560. Springer, 2011. Google Scholar
  10. Oded Goldreich. In a world of p=bpp. In Studies in Complexity and Cryptography, volume 6650 of Lecture Notes in Computer Science, pages 191-232. Springer, 2011. Google Scholar
  11. Oded Goldreich. Introduction to Property Testing. Cambridge University Press, 2017. Google Scholar
  12. Xin Li. Improved constructions of two-source extractors. CoRR, abs/1508.01115, 2015. Google Scholar
  13. Jaikumar Radhakrishnan and Amnon Ta-Shma. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM J. Discret. Math., 13(1):2-24, 2000. Google Scholar
  14. Anup Rao. A 2-source almost-extractor for linear entropy. In APPROX-RANDOM, volume 5171 of Lecture Notes in Computer Science, pages 549-556. Springer, 2008. Google Scholar
  15. Ran Raz and Omer Reingold. On recycling the randomness of states in space bounded computation. In STOC, pages 159-168. ACM, 1999. Google Scholar
  16. Ronen Shaltiel. Recent developments in explicit constructions of extractors. Bull. EATCS, 77:67-95, 2002. Google Scholar
  17. Ronen Shaltiel. An introduction to randomness extractors. In ICALP (2), volume 6756 of Lecture Notes in Computer Science, pages 21-41. Springer, 2011. Google Scholar
  18. Ronen Shaltiel. Weak derandomization of weak algorithms: Explicit versions of yao’s lemma. Comput. Complex., 20(1):87-143, 2011. Google Scholar
  19. Salil P. Vadhan. Pseudorandomness. Found. Trends Theor. Comput. Sci., 7(1-3):1-336, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact