Revision #3 Authors: Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar

Accepted on: 9th July 2016 07:15

Downloads: 279

Keywords:

In this paper we propose a quantification of ensemble 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 an ensemble of distributions is quantitatively equivalent to the notion of \emph{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 an ensemble of distributions on the set of $n$-length 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 needs 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 bit-fixing sources introduced by Chor \emph{et al.}, which we term \emph{nonpseudorandom bit-fixing source}. We adapt the techniques of Gabizon, Raz and Shaltiel to construct a deterministic \emph{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}.

The main change is that in the revised paper we focus on ensemble of distributions rather than on single distributions. Also some technical details in some of the proofs were missing in the earlier version.

Revision #2 Authors: Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar

Accepted on: 9th July 2016 07:12

Downloads: 146

Keywords:

In this paper we propose a quantification of ensemble 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 an ensemble of distributions is quantitatively equivalent to the notion of \emph{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 an ensemble of distributions on the set of $n$-length 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 needs 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 bit-fixing sources introduced by Chor \emph{et al.}, which we term \emph{nonpseudorandom bit-fixing source}. We adapt the techniques of Gabizon, Raz and Shaltiel to construct a deterministic \emph{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}.

The main change is that in the revised paper we focus on ensemble of distributions rather than on single distributions. Also some technical details in some of the proofs were missing in the earlier version.

Revision #1 Authors: Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar

Accepted on: 13th October 2015 11:14

Downloads: 318

Keywords:

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 \emph{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 \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 bit-fixing sources introduced by Chor \emph{et al.}, which we term \emph{nonpseudorandom bit-fixing source}. We adapt the techniques of Gabizon, Raz and Shaltiel to construct a deterministic \emph{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}.

definition of win of an s-gale is different, several proofs have been modified and a few new results on pseudoentropy has been added

TR14-057 Authors: Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar

Publication: 18th April 2014 23:49

Downloads: 892

Keywords:

In this paper, we propose a quantification of distributions on a set

of strings, in terms of how close to pseudorandom the distribution

is. The quantification is an adaptation of the theory of dimension of

sets of infinite sequences first introduced by Lutz

\cite{Lutz:DISS}.

We show that this definition is robust, by considering an alternate, equivalent

quantification. It is known that pseudorandomness can be characterized

in terms of predictors \cite{Yao82a}. Adapting Hitchcock

\cite{Hitchcock:FDLLU}, we show that the log-loss function incurred by

a predictor on a distribution is quantitatively equivalent to the

notion of dimension we define. We show that every distribution on a

set of strings of length $n$ has a dimension $s\in[0,1]$, and for

every $s \in [0,1]$ there is a distribution with dimension $s$. We

study some natural properties of our notion of dimension.

Further, we propose an application of our quantification to the

following problem. If we know that the dimension of a distribution on

the set of $n$-length strings is $s \in [0,1]$, can we

deterministically extract out $sn$ \emph{pseudorandom} bits out of the

distribution? We show that this is possible in a special case - a

notion analogous to the bit-fixing sources introduced by Chor

\emph{et. al.} \cite{CGHFRS85}, which we term a \emph{nonpseudorandom

bit-fixing source}. We adapt the techniques of Kamp and Zuckerman

\cite{KZ03} and Gabizon, Raz and Shaltiel \cite{GRS05} to establish

that in the case of a non-pseudorandom bit-fixing source, we can

deterministically extract the pseudorandom part of the

source. Further, we show that the existence of optimal nonpseudorandom

generator is enough to show ${\P}={\BPP}$.