Dimension, pseudorandomness and extraction of pseudorandomness

Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

In this paper we propose a quantification of distributions on a set of strings, in terms of how close to pseudorandom a distribution is. The quantification is an adaptation of the theory of dimension of sets of infinite sequences introduced by Lutz. Adapting Hitchcock's work, we also show that the logarithmic loss incurred by a predictor on a distribution is quantitatively equivalent to the notion of dimension we define. Roughly, this captures the equivalence between pseudorandomness defined via indistinguishability and via unpredictability. Later we show some natural properties of our notion of dimension. We also do a comparative study among our proposed notion of dimension and two well known notions of computational analogue of entropy, namely HILL-type pseudo min-entropy and next-bit pseudo Shannon entropy. Further, we apply our quantification to the following problem. If we know that the dimension of a distribution on the set of n-length strings is s ∈ (0, 1], can we extract out O(sn) pseudorandom bits out of the distribution? We show that to construct such extractor, one need at least (log n) bits of pure randomness. However, it is still open to do the same using Ω(log n) random bits. We show that deterministic extraction is possible in a special case - analogous to the bitfixing sources introduced by Chor et al., which we term nonpseudorandom bit-fixing source. We adapt the techniques of Gabizon, Raz and Shaltiel to construct a deterministic pseudorandom extractor for this source. By the end, we make a little progress towards P vs. BPP problem by showing that existence of optimal stretching function that stretches O(log n) input bits to produce n output bits such that output distribution has dimension s ∈ (0, 1], implies P=BPP.

Original languageEnglish (US)
Title of host publication35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2015
EditorsPrahladh Harsha, G. Ramalingam
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages221-235
Number of pages15
ISBN (Electronic)9783939897972
DOIs
StatePublished - Dec 1 2015
Event35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2015 - Bangalore, India
Duration: Dec 16 2015Dec 18 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume45
ISSN (Print)1868-8969

Conference

Conference35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2015
Country/TerritoryIndia
CityBangalore
Period12/16/1512/18/15

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Dimension, pseudorandomness and extraction of pseudorandomness'. Together they form a unique fingerprint.

Cite this