Agrawal, Manindra ;
Chakraborty, Diptarka ;
Das, Debarati ;
Nandakumar, Satyadev
Dimension, Pseudorandomness and Extraction of Pseudorandomness
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 HILLtype pseudo minentropy and nextbit 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 nlength strings is s in (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 Omega(log n) bits of pure randomness. However, it is still open to do the same using O(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 bitfixing 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 in (0,1], implies P=BPP.
BibTeX  Entry
@InProceedings{agrawal_et_al:LIPIcs:2015:5618,
author = {Manindra Agrawal and Diptarka Chakraborty and Debarati Das and Satyadev Nandakumar},
title = {{Dimension, Pseudorandomness and Extraction of Pseudorandomness}},
booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
pages = {221235},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897972},
ISSN = {18688969},
year = {2015},
volume = {45},
editor = {Prahladh Harsha and G. Ramalingam},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5618},
URN = {urn:nbn:de:0030drops56184},
doi = {10.4230/LIPIcs.FSTTCS.2015.221},
annote = {Keywords: Pseudorandomness, Dimension, Martingale, Unpredictability, Pseudoentropy, Pseudorandom Extractor, Hard Function}
}
2015
Keywords: 

Pseudorandomness, Dimension, Martingale, Unpredictability, Pseudoentropy, Pseudorandom Extractor, Hard Function 
Seminar: 

35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Issue date: 

2015 
Date of publication: 

2015 